Link to Question

MEDIUM

Jump Game

You are given an array of non-negative integers nums. 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

Input:

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

Output:

true

Explanation:
Jump from index 0 to 1, then from 1 to 4.

---

Constraints

• 1 ≤ nums.length ≤ 10⁴
• 0 ≤ nums[i] ≤ 10⁵

---

Solution: Greedy

• Time Complexity: O(n)
• Space Complexity: O(1)

C++

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