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.

Examples

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. 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

Thinking Process

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.

  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.
1D DP recurrence dp[i] 0 1 2 ? dp[i] from smaller indices / subproblems

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
1D DP (this problem) O(n) O(n) or O(1) Linear recurrence
2D DP O(nm) O(nm) or O(n) Grid or two-sequence problems
State machine DP O(n) O(1) Buy/sell, hold/not-hold states
Memoization (top-down) Same as DP O(n) Recursive + cache

Solution

Solution: Greedy with Rightmost Tracking

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

Solution Explanation

Approach: 1D DP (this problem)

Key idea: 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.

How the code works:

  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.

Walkthrough — input nums = [2,3,1,1,4], expected output true:

Jump 1 step from index 0 to 1, then 3 steps to the last index.

Time: O(n) where n is the length of the array · Space: O(1)

Algorithm Explanation:

  1. Initialize (Lines 4-5):
    • N: Length of the array
    • rightMost: Farthest position we can reach (starts at 0)
  2. Iterate Through Array (Lines 6-11):
    • For each index i:
      • Check reachability: if(i <= rightMost)
        • If current index is reachable, we can jump from here
      • Update rightmost: rightMost = max(rightMost, i + nums[i])
        • From index i, we can reach up to i + nums[i]
        • Update rightMost to the maximum reachable position
      • Early termination: if(rightMost >= N - 1) return true
        • If we can reach the last index, return true immediately
  3. Return (Line 12):
    • If we finish the loop without reaching the last index, return false

Example Walkthrough:

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

Initial: rightMost = 0, N = 5

i=0: nums[0]=2
  Check: 0 <= 0? Yes (reachable)
  Update: rightMost = max(0, 0+2) = 2
  Check: 2 >= 4? No
  Continue

i=1: nums[1]=3
  Check: 1 <= 2? Yes (reachable)
  Update: rightMost = max(2, 1+3) = 4
  Check: 4 >= 4? Yes ✓
  Return: true

Example 2: nums = [3,2,1,0,4]

Initial: rightMost = 0, N = 5

i=0: nums[0]=3
  Check: 0 <= 0? Yes
  Update: rightMost = max(0, 0+3) = 3
  Check: 3 >= 4? No
  Continue

i=1: nums[1]=2
  Check: 1 <= 3? Yes
  Update: rightMost = max(3, 1+2) = 3
  Check: 3 >= 4? No
  Continue

i=2: nums[2]=1
  Check: 2 <= 3? Yes
  Update: rightMost = max(3, 2+1) = 3
  Check: 3 >= 4? No
  Continue

i=3: nums[3]=0
  Check: 3 <= 3? Yes
  Update: rightMost = max(3, 3+0) = 3
  Check: 3 >= 4? No
  Continue

i=4: nums[4]=4
  Check: 4 <= 3? No (not reachable!)
  Cannot update rightMost
  Continue

Loop ends: rightMost = 3 < 4
Return: false

Example 3: nums = [2,0,0]

Initial: rightMost = 0, N = 3

i=0: nums[0]=2
  Check: 0 <= 0? Yes
  Update: rightMost = max(0, 0+2) = 2
  Check: 2 >= 2? Yes ✓
  Return: true

Algorithm Breakdown

Why Greedy Works

The greedy strategy is optimal because:

  1. Local Optimal: At each reachable index, we maximize the rightmost reachable position
  2. No Regret: If we can reach index i, we can always reach any position we could have reached by a different path
  3. Optimal Substructure: The ability to reach the last index depends only on the rightmost reachable position

Key Insight: Rightmost Reachable Position

Instead of tracking all possible positions, we only need to track:

  • The farthest position we can reach from any reachable index
  • If rightMost >= N - 1, we can reach the last index
  • If at any point i > rightMost, we’re stuck (cannot reach index i)

Reachability Check

The condition if(i <= rightMost) ensures:

  • We only update rightMost from positions we can actually reach
  • If i > rightMost, we cannot reach index i, so we cannot jump from there
  • This prevents invalid updates

Time & Space Complexity

  • Time Complexity: O(n) where n is the length of the array
    • Single pass through the array
    • Constant time operations for each element
  • Space Complexity: O(1)
    • Only using a few variables (rightMost, N, i)
    • No additional data structures

Key Points

  1. Greedy Strategy: Track rightmost reachable position
  2. Reachability Check: Only update from reachable indices
  3. Early Termination: Return true as soon as we can reach the last index
  4. Optimal: Greedy approach finds the answer in one pass
  5. Simple: Straightforward implementation

Common Mistakes

  1. Single element: [0] → return true (already at last index)
  2. All zeros except first: [2,0,0,0] → return false
  3. Can reach immediately: [5,1,1,1,1] → return true (jump from index 0)
  4. Zero at start: [0,1,2] → return false (cannot move from index 0)

  5. Large jump: [1,1,1,100] → return true

  6. Not checking reachability: Updating rightMost from unreachable indices
  7. Wrong condition: Using i < rightMost instead of i <= rightMost
  8. Missing early termination: Not checking if we can reach last index early
  9. Wrong update: Not using max() to update rightMost
  10. Index confusion: Off-by-one errors with array indices

Tags

Array, Greedy, Dynamic Programming, Medium

Key Takeaways

  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.

References

Template Reference