Problem description:

/*
Given an array of non-negative integers, 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: [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: [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.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        int lastPos = nums.size() - 1;
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) { //(current position + steps in this position) > lastPos
                lastPos = i;              //if get to this slot, then we can get to last index
            }
        }
        return lastPos == 0;
    }
};

second time:

key point is to determine whether current position+ position value can reach to the end

  • use a pointer reach to denote the farthest position can reach
  • use another pointer i to denote the current position. It should be smaller than array size and reach. Because if i reaches the reach, it means the reach derived from previous steps can not reach to i, so will never reach to position i.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        int reach=0; //where is the farest that it can reach
        int i=0; //current location
        while(i< nums.size() && i<=reach){
            reach=max(reach, i+nums[i]);
            i++;
        }
        
        return reach>=nums.size()-1; //check whether reach is greater than array size
    }
};
1
2
3
4
5
6
7
8
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        m = 0
        for i, n in enumerate(nums):
            if i > m:
                return False
            m = max(m, i + n)
        return True