45. Jump Game II

Problem Statement

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

Intuition

Approach: DP takes n2

But greedy take O(N)
Intuition is that,

We Do like a BFS kind of thing,
We maintain a max jump and if er cross that, we incr jumps

2 3 1 4 5
_ , , | |

From 2 we can in 1 jump reach till 2 index
After that till 5 we can reach in 2 steps

Links

https://leetcode.com/problems/jump-game-ii/description/

Video Links

https://www.youtube.com/watch?v=dJ7sWiOoK7g&ab_channel=NeetCode

Approach 1:

C++

class Solution {
public:
    int jump(vector<int>& arr) {
        int farthest=0;    
        int jumps=0;         
        int current=0;  

        for(int i = 0; i < arr.size()-1; i++) {
            farthest= max(farthest,arr[i]+i);

            if(i==current){
                jumps++;
                current=farthest;
            }

        }
        return jumps; 
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++