Jump Game (#55 Leetcode)

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

 

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

 

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

The task is to determine if we can jump to the last index starting from the first index. We can solve this optimally by working backward.
The idea is to use a "goal" that starts at the last index and moves backward whenever a preceding index can reach or surpass it. If we can move the goal to the first index, the last index is reachable.

If we meet the condition we update goal with current index.

Let's see how it works.

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

We start at the second position from the last.

[2,3,1,1,4]
       i g 

i = current position
g = goal            

Let's use the formula above.

current position + maximum jump >= goal
= 3 + 1 >= 4
= true      

We can reach the current goal(= index 4) from current position(= index 3), that means if we reach index 3, we are sure that we can definitely reach the goal(= the last index).

That's why we can move goal to index 3.

Next,

[2,3,1,1,4]
     i g   

current position + maximum jump >= goal
= 2 + 1 >= 3                           
= true                                 

If true, we are sure we can reach index 3 from index 2. We know that if we reach index 3, we can reach the last index, so update goal with index 2. In the next time, if we can reach index 2, that means we can reach the last index(= 4)

Next,

[2,3,1,1,4]
   i g     

I'll speed up.

current position + maximum jump >= goal
= 1 + 3 >= 2
= true      

[2,3,1,1,4] 
 i g        

current position + maximum jump >= goal
= 0 + 2 >= 1
= true      

In the end,

[2,3,1,1,4]
 g         

Now, goal is index 0. That means we can reach the goal because we start from index 0, so before we return true or false, we check this condition.

if goal == 0

In this case

return true

Please click here to debug this program. 

class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        int goal = nums.size() - 1;
        std::cout << nums.size() - 2 << std::endl;
        for (int i = nums.size() - 2; i >= 0; i-- )
        {
            if (i + nums[i] >= goal) {
            std::cout << "\n" << i << " " << goal << std::endl;
            goal = i;
            }
            std::cout << i << " " << goal << std::endl;
        }
        return goal == 0;
    }
};

Why we can't do it from the left index 0? 

If we start it from the left index, then we need to move the index to the next successive goal everytime. In this case, we need to add more conditions to check if not greater than the last index.