Jump Game II

Share

Find minimum jumps to reach last index.

Example 1
Input: nums=[2,3,1,1,4] → Output: 2
Example 2
Input: nums=[2,3,0,1,4] → Output: 2

Solution Approach

BFS greedy: track current range end and farthest reach.

  • jumps=0, curEnd=0, farthest=0
  • For i from 0 to n-2: farthest = max(farthest, i+nums[i])
  • At i == curEnd: jumps++, curEnd=farthest
  • Return jumps
Java
public int jump(int[] nums) {
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == curEnd) { jumps++; curEnd = farthest; }
    }
    return jumps;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)