Problem Statement

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

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.

Problem Link

Jump Game - LeetCode

Code

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int currEnd = 0, maxRange = 0;
        
        for(int i=0;i<n;i++)
        {
            maxRange = max(maxRange,nums[i]+i);
            
            if(currEnd<i)
                return false;
            
            if(i<n-1 and currEnd==i)
                currEnd = maxRange;
        }
        return true;
        
    }
};

Time complexity O(n)

Space complexity O(1)

Another approach

Intuition

Imagine you have a car, and you have some distance to travel (the length of the array). This car has some amount of gasoline, and as long as it has gasoline, it can keep traveling on this road (the array). Every time we move up one element in the array, we subtract one unit of gasoline. However, every time we find an amount of gasoline that is greater than our current amount, we "gas up" our car by replacing our current amount of gasoline with this new amount. We keep repeating this process until we either run out of gasoline (and return false), or we reach the end with just enough gasoline (or more to spare), in which case we return true.

Note: We can let our gas tank get to zero as long as we are able to gas up at that immediate location (element in the array) that our car is currently at.

Complexity