LeetCode · #45

Jump Game II Solution

Return the minimum number of jumps to reach the last index. You can always reach the end.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #45

🏗️

Pattern

Greedy — BFS levels on array

Given array nums where nums[i] is the max jump from index i, return the minimum number of jumps to reach the last index. Guaranteed reachable.

Example

Input: nums = [2,3,1,1,4]
Output: 2 // Jump 1→index 1, then 3→index 4.  Two jumps.

Constraints

• 1 ≤ nums.length ≤ 10⁴ • 0 ≤ nums[i] ≤ 1000

Section Two · Approach 1

DP — O(n²)

dp[i] = minimum jumps to reach index i. For each i, check all j < i that can reach i: dp[i] = min(dp[j] + 1).

Why we can do better

Problem: O(n²) inner loop. The insight: think of jumps as BFS levels. Level 0 = index 0. Level 1 = all indices reachable from index 0. Level 2 = all indices reachable from level 1. Track the current level's boundary and the farthest reach — increment jumps when you pass a boundary.

Java — DP O(n²)

 class Solution {
public int jump(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
        java.util.Arrays.fill(dp, n);
        dp[0] = 0;
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (j + nums[j] >= i) dp[i] = Math.min(dp[i], dp[j] + 1);
return dp[n - 1];
    }
}

Python — DP O(n²)

 class Solution:
def jump(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [float('inf')] * n
        dp[0] = 0 for i in range(1, n):
for j in range(i):
if j + nums[j] >= i:
                    dp[i] = min(dp[i], dp[j] + 1)
return dp[-1]

Metric	Value
Time	O(n²)
Space	O(n)

Section Three · Approach 2

BFS-Greedy — O(n) time, O(1) space

Treat the array as a BFS graph: each "level" = one jump. Track curEnd (end of current level) and farthest (farthest reach from current level). When i passes curEnd, increment jumps and set curEnd = farthest.

💡 Mental model: Imagine a frog crossing a river on lily pads. Each pad says "you can jump up to X pads forward." The frog wants minimum hops. It looks at all pads reachable from its current hop, picks the one that extends farthest (not necessarily the biggest jump — the one that gets closest to shore), and hops. Each "look at all reachable pads" is one BFS level = one jump.

Algorithm

jumps = 0, curEnd = 0, farthest = 0.
For i from 0 to n-2 (don't need to jump FROM the last index):
farthest = max(farthest, i + nums[i]).
If i == curEnd: jumps++, curEnd = farthest.
Return jumps.

🎯 When to recognize this pattern: "Minimum steps/jumps to reach end" on a 1D array. The BFS-level abstraction works because each jump = one BFS level, and you want the fewest levels. Also applicable to minimum number of coins, minimum operations, etc. when structure allows greedy BFS.

Section Four · Trace

Visual Walkthrough

Trace for nums = [2, 3, 1, 1, 4].

Jump Game II — BFS Levels

Section Five · Implementation

Code — Java & Python

Java — BFS-Greedy

 class Solution {
public int jump(int[] nums) {
int jumps = 0, curEnd = 0, farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
if (i == curEnd) { // end of current BFS level
jumps++;
                curEnd = farthest;
            }
        }
return jumps;
    }
}

Python — BFS-Greedy

 class Solution:
def jump(self, nums: list[int]) -> int:
        jumps = cur_end = farthest = 0 for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
if i == cur_end:
                jumps += 1
cur_end = farthest
return jumps

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
DP	O(n²)	O(n)	Standard but quadratic
BFS explicit queue	O(n)	O(n)	Queue overhead
BFS-Greedy ← optimal	O(n)	O(1)	Implicit BFS with two pointers

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single element	`[0]`	Already at end. 0 jumps.
Two elements	`[1,0]`	One jump from 0→1. Return 1.
Max first jump	`[5,0,0,0,0,0]`	One jump covers entire array.
Step by step	`[1,1,1,1]`	Must jump one at a time. 3 jumps.

⚠ Common Mistake: Iterating to i < n instead of i < n-1. If you process the last index, you might increment jumps unnecessarily when i == curEnd == n-1. You never need to jump from the last index — only to it. Stop the loop at n-2.

← Back to Greedy problems

LearningTree

LC 45 · Jump Game II — Solution & Explanation | DSA Guide