loading

55. Jump Game — Step-by-Step Visualization

mediumLeetCode #55ArrayGreedy

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

Algorithm Pattern

Greedy / Max Reach

Key Idea

Keep track of the furthest index we can currently reach (`max_reach`). As we iterate through the array, if we ever find ourselves at an index that exceeds our current `max_reach`, we know the end is unreachable. Otherwise, we update `max_reach` to be the maximum of itself and `i + nums[i]`.

Step-by-Step Approach

  1. Initialize `maxReach = 0`.
  2. Iterate through each index `i` of the array:
  3. 1. If `i > maxReach`, return `false` (we can't reach this index).
  4. 2. Update `maxReach = max(maxReach, i + nums[i])`.
  5. 3. If `maxReach >= lastIndex`, return `true` (we can reach the end).
  6. If we finish the loop, we successfully reached the end.

Common Gotchas

  • The greedy approach is O(n), which is much faster than Dynamic Programming (O(n^2)) for this specific problem.
  • Ensure you handle the case where the first element is 0 and the array has more than one element.

Related Problems

← All problems