Log inSign up
mediumLeetCodeNot Started

Jump Game II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

You are given a 0-indexed array of integers nums of length N. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where: - 0 <= j <= nums[i] and - i + j < N

Return the minimum number of jumps to reach index N - 1. You can assume that you can always reach the last index.

Example 1 · Example 1: Five Elements:

Input: nums = [2, 3, 1, 1, 4]
Output: 2
Explanation: The minimum number of jumps is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2 · Example 2: Direct Jump Possibility:

Input: nums = [2, 3, 0, 1, 4]
Output: 2
Explanation: Jump from index 0 to 1 (1 jump), then index 1 to 4 (1 jump). Total = 2.

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • It's guaranteed that you can reach nums[n - 1].

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the implicit BFS window abstraction for interval jumping.
  • Explain why updating currentEnd avoids choosing specific landing indices.
  • Implement the O(N) greedy window solution across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find minimum jumps/steps to reach end of array.
  • Each index gives maximum forward reach.
  • Guaranteed reachability.

Algorithmic Decision Tree:

  • Jump Game I: Boolean reachability -> track maxReach.
  • Jump Game II: Min jumps count -> track currentEnd and maxReach (level BFS).

Connected Patterns:

Jump GameVideo StitchingMinimum Number of Taps to Open to Water a Garden

1. Recursive Minimum Jump Search

Intuition

Recursively explore every valid forward jump from the current index, returning 1 + minimum jumps across all choices.

Algorithm

  1. Step 1: If current index >= n - 1, return 0 (no further jumps needed).
  2. Step 2: Initialize minJumps = infinity.
  3. Step 3: Loop step from 1 to nums[i], recursing on i + step.
  4. Step 4: Update minJumps = min(minJumps, 1 + recursiveResult).
  5. Step 5: Return minJumps.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int idx, const vector<int>& nums) {
9 if (idx >= (int)nums.size() - 1) return 0;
10 int minJumps = 1e9;
11 int furthest = min(idx + nums[idx], (int)nums.size() - 1);
12 for (int next = idx + 1; next <= furthest; ++next) {
13 minJumps = min(minJumps, 1 + solve(next, nums));
14 }
15 return minJumps;
16 }
17public:
18 int jump(vector<int>& nums) {
19 return solve(0, nums);
20 }
21};
22
23int main() {
24 Solution sol;
25 vector<int> nums = {2, 3, 1, 1, 4};
26 cout << "Min Jumps: " << sol.jump(nums) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(2^N)
  • Space complexity: O(N)

2. Dynamic Programming (Tabulation)

Intuition

Define dp[i] as the minimum jumps needed to reach index i from 0. Initialize dp[0] = 0 and all other entries to infinity, propagating forward.

Algorithm

  1. Step 1: Initialize dp array of size n with infinity, set dp[0] = 0.
  2. Step 2: For each i from 0 to n - 1:
  3. Step 3: If dp[i] is reachable, iterate j from i + 1 up to min(i + nums[i], n - 1).
  4. Step 4: Update dp[j] = min(dp[j], dp[i] + 1).
  5. Step 5: Return dp[n - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int jump(vector<int>& nums) {
10 int n = nums.size();
11 vector<int> dp(n, 1e9);
12 dp[0] = 0;
13
14 for (int i = 0; i < n; ++i) {
15 if (dp[i] == 1e9) continue;
16 int furthest = min(i + nums[i], n - 1);
17 for (int j = i + 1; j <= furthest; ++j) {
18 dp[j] = min(dp[j], dp[i] + 1);
19 }
20 }
21
22 return dp[n - 1];
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<int> nums = {2, 3, 1, 1, 4};
29 cout << "Min Jumps (DP): " << sol.jump(nums) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N^2)
  • Space complexity: O(N)

3. Greedy Window / Implicit BFS

Intuition

Maintain the current jump window boundary currentEnd and track furthest reachable index maxReach. Increment jumps when the index reaches currentEnd.

Algorithm

  1. Step 1: If n <= 1, return 0.
  2. Step 2: Initialize jumps = 0, currentEnd = 0, maxReach = 0.
  3. Step 3: Iterate through index i from 0 up to n - 2 (stop before the last index).
  4. Step 4: Update maxReach = max(maxReach, i + nums[i]).
  5. Step 5: If i reaches currentEnd, increment jumps and advance currentEnd = maxReach.
  6. Step 6: Return jumps.

Interactive Trace for Jump Game II

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: At index 0 (nums[0] = 2)
Visual state
Values and pointers at this exact step
pointers
S
jump 1 boundary
reachable
window end
unreached
target
0
↑ i
1
2
↑ currentEnd
3
4
Check / comparison
i == currentEnd (0 == 0)
Decision / next transition
jumps = 1, currentEnd = 2, maxReach = 2.
Why this step matters

Step 1: At index 0 (nums[0] = 2). maxReach becomes max(0, 0 + 2) = 2. Since i == currentEnd (0), increment jumps to 1 and update currentEnd = 2.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int jump(vector<int>& nums) {
10 int n = nums.size();
11 if (n <= 1) return 0;
12
13 int jumps = 0, currentEnd = 0, maxReach = 0;
14
15 for (int i = 0; i < n - 1; ++i) {
16 maxReach = max(maxReach, i + nums[i]);
17 if (i == currentEnd) {
18 jumps++;
19 currentEnd = maxReach;
20 if (currentEnd >= n - 1) break;
21 }
22 }
23
24 return jumps;
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<int> nums = {2, 3, 1, 1, 4};
31 cout << "Min Jumps (Greedy): " << sol.jump(nums) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Recursive Path SearchO(2^N)O(N)Recursively try every jump length from 1 up to nums[i], taking the minimum jump count returned.Exponential overlapping recursive calls.
2.Better — Dynamic Programming (Tabulation)O(N^2)O(N)dp[i] represents the min jumps needed to reach index i from index 0. For each i, update dp[j] = min(dp[j], dp[i] + 1) for all j <= i + nums[i].Multiple updates for every reachable target.
3.Optimal — Greedy Window / Implicit BFSOptimalO(N)O(1)Scan from 0 to n - 2. Continuously update maxReach = max(maxReach, i + nums[i]). When i reaches currentEnd, increment jumps and set currentEnd = maxReach.Single linear traversal.
Back to DSA Sheet