Skip to content

Volume ITechnology

4.26.3 — Jump Game II ​

LeetCode 45 · Medium

The problem ​

Same array as 4.26.2 — nums[i] is the maximum jump length from index i. You are guaranteed the end is reachable. Return the minimum number of jumps to get there.

Restating the Problem: You need to find the shortest path to the last index. Because we want the minimum jumps, we want each jump to take us to the most advantageous position for our next jump.

  • Constraints to note: The array length can be up to 10^4. An O(n^2) solution will likely fail, so we need O(n).
  • Edge cases: If the array has only 1 element [0], you are already at the end and require 0 jumps.
[2,3,1,1,4]   →  2     (index 0 → 1 → 4)
[2,3,0,1,4]   →  2

The brute force, and where it wastes work ​

The naive approach is to use a 1D DP array where dp[i] stores the minimum jumps needed to reach the end from index i. For each index, you would check all reachable indices i + 1 to i + nums[i] and take the minimum of those values plus 1. This takes O(n^2) time because for each index, you might scan up to n elements ahead. This is too slow.

The pattern ​

"Fewest steps" says BFS, and that instinct is right — but you do not need a queue.

Think of the indices in levels, exactly like a breadth-first search:

  • Level 0 — index 0.
  • Level 1 — everything reachable in one jump from level 0.
  • Level 2 — everything reachable in one jump from anything in level 1.

The number of jumps is the level the last index lands in.

And because reachability is downward closed (the argument from 4.26.2), each level is a contiguous range of indices. So a level is described by two numbers — where it ends, and how far the next level reaches — and no queue is needed.

That is the whole solution: sweep left to right, and every time you reach the end of the current level, take a jump.

The solution ​

python
class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0  # (1)
        current_end = 0        # (2) last index of the current level
        furthest = 0           # (3) furthest index the next level reaches

        for i in range(len(nums) - 1):        # (4) note: stop BEFORE the last index
            furthest = max(furthest, i + nums[i])  # (5)

            if i == current_end:              # (6) level exhausted → must jump
                jumps += 1  # (7)
                current_end = furthest  # (8)

        return jumps  # (9)
ts
function jump(nums: number[]): number {
  let jumps = 0, currentEnd = 0, furthest = 0;  // (1)

  for (let i = 0; i < nums.length - 1; i++) {  // (4)
    furthest = Math.max(furthest, i + nums[i]);  // (5)

    if (i === currentEnd) {  // (6)
      jumps++;  // (7)
      currentEnd = furthest;  // (8)
    }
  }

  return jumps;  // (9)
}

Line by line ​

Think of the positions in levels, as in a breadth-first search. Level 0 is position 0. Level 1 is every position one jump can reach. Level 2 is every position two jumps can reach, and so on. The answer is the level of the last position.

(1) Jumps made so far.

(2) current_end is the last position in the current level. Every position up to here can be reached with jumps jumps.

(3) furthest is the furthest position the next level reaches: the furthest any position in the current level can jump to.

(4) Walk every position except the last. We stop before the last one, because once we are there no more jumps are needed. If the loop included it, a final unnecessary jump could be counted.

(5) Update how far the next level reaches.

(6) We have reached the end of the current level.

(7) Taking one more jump is now unavoidable, so count it,

(8) and the next level becomes the current one. Its last position is the furthest reach we found.

(9) The number of jumps. The problem promises the last position can be reached.

Three details, and each one matters.

Code Walkthrough:

  • Initialization: jumps counts how many times we've jumped. current_end is the farthest we can reach with our current number of jumps. furthest is the maximum reach we've found so far for the next jump.
  • Iteration: We loop from 0 to len(nums) - 2. We stop before the last index.
  • Updating Reach: At each index i, we see if i + nums[i] extends our furthest possible reach.
  • Taking a Jump (i == current_end): If we reach the end of the current jump's range (current_end), we are forced to take another jump to keep moving. We increment jumps and update current_end to furthest, essentially stepping into the next level of the BFS.

The loop stops at len(nums) - 1, not at the end. Standing on the final index means you have arrived, so no jump is taken from it. Including it would count one jump too many — this is the off-by-one this problem is built around.

furthest accumulates across the whole level before it is used. That is what makes the choice optimal: when the jump is finally taken, it goes to the best possible landing area reachable from anywhere in the current level, not just from the position where the decision was made.

i == current_end is the trigger. You have walked to the last index of the current level, so any further progress needs another jump.

Trace ​

[2,3,1,1,4]

ii + nums[i]furthestat level end?jumpsnew end
022yes (0 == 0)12
144no12
234yes (2 == 2)24
3——loop stops at index 3 (len-1 = 4)

Answer 2 ✓.

Notice index 1 contributed furthest = 4 while the jump was not taken until index 2. That is the point of accumulating first — the jump made at index 2 uses the reach discovered at index 1.

Why greedy is optimal here ​

The exchange argument: suppose an optimal solution uses jump k to land somewhere inside the range that greedy's jump k covers. Since greedy's jump reaches at least as far, you can replace the optimal jump with greedy's without ever needing more jumps later — everything the optimal solution could reach afterwards, greedy can also reach.

"Greedy's reach after k jumps is at least as large as any strategy's reach after k jumps." By induction, greedy never needs more jumps.

That is the shape of a greedy proof: show the greedy state dominates every alternative at each step. 4.25 formalises it.

Edge cases ​

  • One position. The loop never runs, and the answer is 0 jumps.
  • The first jump reaches the end. One jump.
  • Every jump is length 1. You must step on every position, so n − 1 jumps.

Complexity ​

O(n) time, O(1) space.

  • Time Complexity: O(n). We iterate through the array once. Each step performs a constant amount of work (checking max and simple conditionals).
  • Space Complexity: O(1). We only maintain three variables (jumps, current_end, furthest), regardless of input size.

The DP version — dp[i] = fewest jumps to reach i — is O(n^2) and O(n) space. Write the greedy.

Where this goes next ​

  • Jump Game — can you get there at all. 4.26.2.
  • Minimum Number of Taps to Water a Garden and Video Stitching — identical structure in interval clothing. Each tap or clip covers a range; you want the fewest ranges covering [0, n]. Convert each to "furthest reach from position i" and this exact loop solves them. Recognising that these are Jump Game II is worth more than either solution.
  • Jump Game VI — a maximum over a sliding window of previous states, which needs a monotonic deque (4.6.6).

What the interviewer will push on ​

"Why does the loop stop one short?" Arriving at the last index means you are done; no jump is taken from it.

"Why accumulate furthest before jumping?" So the jump uses the best reach available anywhere in the current level.

"Prove the greedy is optimal." Greedy's reach after k jumps dominates any other strategy's reach after k jumps.

"How is this BFS?" Levels are jump counts, and because each level is a contiguous range, two integers replace the queue.

"What is the DP version?" O(n^2) — and say why the greedy beats it.

One thing to volunteer: describe it as BFS without a queue. That framing explains both the level structure and why the answer is the level number, and it makes the two-variable code look inevitable rather than clever.

Next: 4.26.4 Gas Station — a greedy whose proof is the entire problem.

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