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].

submission

impl Solution {
    // BFS solution, this is somewhat easier to understand but still
    // remains O(n) time complexity and O(1) space
    // since the range we could jump to is continuous, we could use a
    // simple [left, right) range to record it.
    // we update the farthest index we could jump to at each step
    // and end if n - 1 is inside range [left, right), that is:
    //    left <= n - 1 && n - 1 < right
    // or simply: right >= n
    pub fn jump(nums: Vec<i32>) -> i32 {
        let (mut left, mut right) = (0, 1);
        let mut steps = 0;
        // !(right >= n)
        while right < nums.len() {
            // update the farthest index we could jump to
            let reach = (left..right).fold(right, |init, val| {
                // don't forget +1 since right is open
                init.max(val + nums[val] as usize + 1)
            });
            // if we are not guaranteed to reach n - 1, this would
            // be wrong, assuming this function returns -1 when
            // unreachable, we could add early return to fix it
            // if reach <= right {
            //     return -1;   
            // }
            (left, right) = (right, reach);
            steps += 1;
        }
        steps
    }
}