Jump Game II

Share

Find minimum number of jumps to reach last index (always reachable).

Example 1
Input: nums=[2,3,1,1,4] → Output: 2. Jump 1->3->4.
Example 2
Input: nums=[2,3,0,1,4] → Output: 2

Solution Approach

BFS-like greedy: track current level end and farthest reachable. When we pass level end, increment jumps.

  • Track jumps=0, curEnd=0, farthest=0
  • For i from 0 to n-2
  • Update farthest = max(farthest, i+nums[i])
  • When 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)