Skip to content

45. Jump Game II

Description

You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0.

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at index i, you can jump to any index (i + j) where:

  • 0 <= j <= nums[i] and
  • i + j < n

Return the minimum number of jumps to reach index n - 1. The test cases are generated such that you can reach index n - 1.

 

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

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

 

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • It's guaranteed that you can reach nums[n - 1].

Solutions

Solution 1: Greedy Algorithm

Thinking

The first idea is DP: \(f[i]\) is the fewest jumps to \(i\), and from \(i\) we relax \(i+1..i+\textit{nums}[i]\). Correct, worst-case \(O(n^2)\). \(n \le 10^4\) may pass, but we only need the end, not a value at every index.

The bottleneck is maintaining exact min jumps per position. Jump \(k\) covers a contiguous range; the farthest we can see inside it is the right end of jump \(k+1\).

Scan once, tracking this jump's boundary and the farthest the next jump can reach. Hitting the boundary forces a jump. That is BFS by layers without a queue.

We can use a variable \(mx\) to record the farthest position that can be reached from the current position, a variable \(last\) to record the position of the last jump, and a variable \(ans\) to record the number of jumps.

Next, we traverse each position \(i\) in \([0,..n - 2]\). For each position \(i\), we can calculate the farthest position that can be reached from the current position through \(i + nums[i]\). We use \(mx\) to record this farthest position, that is, \(mx = max(mx, i + nums[i])\). Then, we check whether the current position has reached the boundary of the last jump, that is, \(i = last\). If it has reached, then we need to make a jump, update \(last\) to \(mx\), and increase the number of jumps \(ans\) by \(1\).

Finally, we return the number of jumps \(ans\).

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

Similar problems:

1
2
3
4
5
6
7
8
9
class Solution:
    def jump(self, nums: List[int]) -> int:
        ans = mx = last = 0
        for i, x in enumerate(nums[:-1]):
            mx = max(mx, i + x)
            if last == i:
                ans += 1
                last = mx
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int jump(int[] nums) {
        int ans = 0, mx = 0, last = 0;
        for (int i = 0; i < nums.length - 1; ++i) {
            mx = Math.max(mx, i + nums[i]);
            if (last == i) {
                ++ans;
                last = mx;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int jump(vector<int>& nums) {
        int ans = 0, mx = 0, last = 0;
        for (int i = 0; i < nums.size() - 1; ++i) {
            mx = max(mx, i + nums[i]);
            if (last == i) {
                ++ans;
                last = mx;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func jump(nums []int) (ans int) {
    mx, last := 0, 0
    for i, x := range nums[:len(nums)-1] {
        mx = max(mx, i+x)
        if last == i {
            ans++
            last = mx
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function jump(nums: number[]): number {
    let [ans, mx, last] = [0, 0, 0];
    for (let i = 0; i < nums.length - 1; ++i) {
        mx = Math.max(mx, i + nums[i]);
        if (last === i) {
            ++ans;
            last = mx;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
impl Solution {
    pub fn jump(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut mx = 0;
        let mut last = 0;
        for i in 0..(nums.len() - 1) {
            mx = mx.max(i as i32 + nums[i]);
            if last == i as i32 {
                ans += 1;
                last = mx;
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public class Solution {
    public int Jump(int[] nums) {
        int ans = 0, mx = 0, last = 0;
        for (int i = 0; i < nums.Length - 1; ++i) {
            mx = Math.Max(mx, i + nums[i]);
            if (last == i) {
                ++ans;
                last = mx;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int jump(int* nums, int numsSize) {
    int ans = 0;
    int mx = 0;
    int last = 0;
    for (int i = 0; i < numsSize - 1; ++i) {
        mx = (mx > i + nums[i]) ? mx : (i + nums[i]);
        if (last == i) {
            ++ans;
            last = mx;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function jump($nums) {
        $ans = 0;
        $mx = 0;
        $last = 0;

        for ($i = 0; $i < count($nums) - 1; $i++) {
            $mx = max($mx, $i + $nums[$i]);
            if ($last == $i) {
                $ans++;
                $last = $mx;
            }
        }

        return $ans;
    }
}

Comments