Skip to content

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 ​

The brute force, and where it wastes work ​

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  # (1)

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

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

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

  return true;  // (6)
}

Line by line ​

(1) furthest is the furthest position we know we can reach. At the start, only position 0.

(2) Walk the positions in order. n is the longest jump allowed from position i.

(3) If this position is beyond the furthest we can reach, we are stuck. Nothing earlier could jump this far, so nothing later can be reached either. Return False.

(4) From here we can jump as far as i + n. Keep the furthest reach seen so far. We do not need to know which jumps to take, only how far we could get.

(5) If we can already reach the last position, stop early with True.

(6) The loop finished without getting stuck, so every position, including the last, was reachable.

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.

Edge cases ​

  • One position. You are already at the end, so True.
  • A zero you can jump over, like [2, 0, 1]. Position 0 reaches position 2 directly, so True.
  • A zero you cannot get past, like [3, 2, 1, 0, 4]. Every jump lands on or before position 3, so position 4 is never reached.

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.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet