M.A.T.R.I.X

Appearance

Volume ITechnology

4.26.2 — Jump Game ​

LeetCode 55 · Medium · ★ Blind 75

The problem ​

nums[i] is the maximum number of steps you can jump forward from index i. Starting at index 0, can you reach the last index?

Restating the Problem: You are placed at the start of an array. Each number tells you the maximum jump you can make from that spot. For example, if you are on a 3, you can jump 1, 2, or 3 steps forward. Your goal is simply to answer "yes" or "no": is it possible to reach (or jump past) the final index?

  • Constraints to note: The array length can be up to 10^4. An O(n^2) solution might barely pass or TLE depending on the language, so an O(n) solution is preferred.
  • Edge cases: The array could have only 1 element [0]. You are already at the last index, so the answer is true. Arrays with 0s are the only real obstacles.
[2,3,1,1,4]   →  true    (jump 1 to index 1, then 3 to the end)
[3,2,1,0,4]   →  false   (every route lands on the 0 at index 3)

The pattern ​

Brute Force / DP Approach ​

The naive approach is to use Recursion with Memoization (Top-Down DP) or Bottom-Up DP. From each index i, we can try jumping 1, 2, ..., nums[i] steps forward. If any of those reachable indices can reach the end, then index i can also reach the end.

The DP version asks, for every index, whether the end is reachable from it. This takes O(n^2) time because for each of the n indices, we might check up to n possible jumps. With n = 10^4, n^2 = 10^8 operations, which is slow and wastes effort checking the same paths multiple times.

The greedy version is one pass, and it comes from a single realisation:

You do not care about the route. You only care how far you can get.

Walk left to right, carrying furthest — the largest index reachable so far. At each position i:

  • If i > furthest, you cannot even stand here. Return false.
  • Otherwise update furthest = max(furthest, i + nums[i]).

If you get through the loop, the end is reachable.

Why the greedy is correct ​

Worth proving, because "track the furthest reach" sounds too simple.

Every index up to furthest is reachable. Reachability here is downward closed: if you can jump from i to i + nums[i], you can also stop at any index in between, since nums[i] is a maximum and shorter jumps are allowed.

So there is no need to track which indices are reachable — a single number describes the whole set. That is why one variable suffices and why no path needs remembering.

The word "maximum" in the problem statement is doing the work. If jumps had to be exact, the reachable set would be full of holes and this argument would collapse. That is the assumption to name.

The solution ​

python
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        furthest = 0

        for i, n in enumerate(nums):
            if i > furthest:
                return False                  # cannot even reach this index
            furthest = max(furthest, i + n)
            if furthest >= len(nums) - 1:
                return True                   # early exit

        return True
ts
function canJump(nums: number[]): boolean {
  let furthest = 0;

  for (let i = 0; i < nums.length; i++) {
    if (i > furthest) return false;
    furthest = Math.max(furthest, i + nums[i]);
    if (furthest >= nums.length - 1) return true;
  }

  return true;
}

Code Walkthrough:

  • Initialization: We start with furthest = 0, representing the maximum index we know we can reach so far.
  • Iteration: We loop through each index i and its value n.
  • Liveness Check (i > furthest): Before we can jump from i, we must ensure we can actually reach i. If i is strictly greater than furthest, it means we are stuck at some earlier zero and cannot progress. We return False.
  • Update Reach (max(furthest, i + n)): If we can reach i, we see if jumping from i gets us further than our current furthest record.
  • Early Exit (furthest >= len(nums) - 1): If our reach includes or exceeds the last index, we can safely return True immediately, saving time.

Check i > furthest before updating. You must be able to stand on i before you can jump from it. Updating first would let a stranded index contribute its jump.

The early exit is optional but free, and it makes the common case fast.

furthest starts at 0, because you begin at index 0 with no jumps taken.

Trace ​

[3,2,1,0,4]

ireachable?i + nums[i]furthest
0yes (0 ≤ 0)33
1yes (1 ≤ 3)33
2yes33
3yes33
4no (4 > 3)—return false

The 0 at index 3 is the wall. Nothing before it reaches past index 3.

The backwards version ​

There is an equally clean solution that walks from the right:

python
goal = len(nums) - 1
for i in range(len(nums) - 2, -1, -1):
    if i + nums[i] >= goal:
        goal = i                      # this index can reach the goal, so it becomes the goal
return goal == 0

Read it as "can anything reach the goal? if so, that becomes the new goal", shrinking the target leftwards. If the goal reaches index 0, the start can reach the end.

Same complexity. Some people find it more obviously correct because it never has to argue about reachable sets. Know both and pick the one you can explain fastest.

Complexity ​

O(n) time, O(1) space — against O(n^2) time and O(n) space for the DP.

  • Time Complexity: O(n). We do a single pass through the array. At each step, we do constant time operations (a comparison and a max).
  • Space Complexity: O(1). We only track a single integer furthest (or goal in the backwards version). No extra memory proportional to the input size is used.

Where this goes next ​

  • Jump Game II — the fewest jumps, not just whether it is possible. The greedy becomes a level-by-level sweep. 4.26.3.
  • Jump Game III — jumps go both directions, so reachability is no longer downward closed and the greedy collapses. It becomes BFS or DFS on a graph. That contrast is worth holding: the greedy here depends entirely on moving forward only.
  • Jump Game IV, VI — BFS and DP with a monotonic deque respectively.
  • Video Stitching, Minimum Number of Taps to Water a Garden — interval-covering problems with the same "furthest reach" structure.

What the interviewer will push on ​

"Why does tracking one number work?" Reachability is downward closed, because nums[i] is a maximum and you may jump less. So the reachable set is always a prefix, and a prefix is described by its end.

"Where does the word maximum matter?" If jumps were exact, the reachable set would have holes and the argument fails.

"Why check i > furthest first?" You must be able to stand somewhere before jumping from it.

"What is the DP solution and why is it worse?" O(n^2) checking every reachable index from every position.

"What if you could jump backwards too?" The greedy breaks; it becomes a graph search.

One thing to volunteer: give the downward-closed argument before writing the loop. Greedy solutions are only convincing with the reason attached, and 4.25 makes that the whole point of the chapter.

Next: 4.26.3 Jump Game II — the same array, now counting jumps, and the greedy turns into a level sweep.