45. Jump Game II

This is the 10th problem of Top Interview 150 LeetCode study plan. At first simply tried a brute-force which exceeded the time limit 😅.

Problem description

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

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

0 <= j <= nums[i] and

i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[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].

Problem solution

Intuition

Calculate the farthest destination you could jump on each step and make the next jumping decision that optimizes the number of jumps.

Approach

Initial Setup: We start at the first position with an index of 0.

First Jump: At index 0, we have a jump of 2. So, our reachable positions are indices 1 and 2.

Max Reach: Among the reachable positions, the farthest we can reach is index 2 (because we can jump to index 2 from index 0). So, maxReach is updated to 2.

Jump Decision: Since we have multiple choices (indices 1 and 2), we choose to jump to index 1. This is because it's the farthest reachable position with the current jump.

Next Jump: After making the jump to index 1, we have a jump of 3 from there. So, our reachable positions are indices 2, 3, and 4.

Max Reach Update: Among the reachable positions, the farthest we can reach is index 4 (because we can jump to index 4 from index 1). So, maxReach is updated to 4.

Jump Decision: Since we have multiple choices (indices 2, 3, and 4), we choose to jump to index 4. This is because it's the farthest reachable position with the current jump.

End Reached: We've reached the end of the array, so we return the number of steps taken, which is 2.

So, by always choosing the position that maximizes our reach at each step, we're able to reach the end of the array with the minimum number of jumps, which in this case is 2.

Complexity

Time complexity: We iterates the array once, so time complexity is O(n)

Space complexity: We uses constant space. So, space complexity is O(1)

Code


public class Solution {
    public int Jump(int[] nums) {
        int maxReach = 0;
        int lastJump = 0;
        int steps = 0;
        for(int i = 0; i<nums.Length; i++) {
            if(i > lastJump) {
                lastJump = maxReach;
                steps+=1;
            }
            maxReach = Math.Max(maxReach, i + nums[i]);
        }
        return steps;
    }
}