55. Jump Game

Posted on Edited on In

55. Jump Game

Description

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:

1
2
3
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:

1
2
3
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 <= 10^4
  • 0 <= nums[i] <= 10^5

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int end = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i > end) {
                return false;
            }
            end = max(end, i + nums[i]);
        }
        return true;
    }
};