Log inSign up
mediumGeeksforGeeksNot Started

Minimum Jumps to Reach End

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

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element nums[i] represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index (or return -1 if unreachable).

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

### Example 2 - Input: nums = [2, 3, 0, 1, 4] - Output: 2

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000

What You'll Learn

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

  • Understand the transition from O(n2) 1D DP to O(n) greedy range expansion.
  • Visualize jumps as levels in a Breadth-First Search (BFS).
  • Avoid unnecessary jumps after reaching the destination boundary.

Pattern Recognition Trigger

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

Signals to Look For:

  • 1D array with forward jump capacities.
  • Finding minimum jumps or steps to reach target index.

Algorithmic Decision Tree:

  • If nums[0] == 0 and n > 1, destination is unreachable (-1).
  • Iterate up to n - 2 (no need to jump once reaching the last index).

Connected Patterns:

Jump GameJump Game VIIVideo Stitching

1. Recursive Exhaustive Search

Intuition

From index i, recursively try all jump lengths from 1 to nums[i] and take the minimum.

Algorithm

  1. Define solve(i).
  2. If i >= n - 1, return 0.
  3. If nums[i] == 0, return \infty.
  4. Try every step s from 1 to nums[i]:
  5. minJumps = min(minJumps, 1 + solve(i + s)).
  6. 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 i, const vector<int>& nums) {
9 if (i >= nums.size() - 1) return 0;
10 if (nums[i] == 0) return 1e9;
11
12 int minJumps = 1e9;
13 for (int step = 1; step <= nums[i]; ++step) {
14 minJumps = min(minJumps, 1 + solve(i + step, nums));
15 }
16 return minJumps;
17 }
18public:
19 int jump(vector<int>& nums) {
20 int ans = solve(0, nums);
21 return ans >= 1e9 ? -1 : ans;
22 }
23};
24
25int main() {
26 Solution sol;
27 vector<int> nums = {2, 3, 1, 1, 4};
28 cout << "Min Jumps: " << sol.jump(nums) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(k^n) where k is average jump
  • Space complexity: O(n) call stack

2. 1D Bottom-Up DP (O(n^2) Time)

Intuition

Build an array dp where dp[i] is the minimum jumps needed to reach the end from index i.

Algorithm

  1. Initialize dp array of size n with \infty.
  2. Set dp[n - 1] = 0.
  3. For i from n - 2 down to 0:
  4. For step from 1 to min(nums[i], n - 1 - i):
  5. dp[i] = min(dp[i], 1 + dp[i + step]).
  6. Return dp[0].
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[n - 1] = 0;
13
14 for (int i = n - 2; i >= 0; --i) {
15 int maxReach = min(i + nums[i], n - 1);
16 for (int j = i + 1; j <= maxReach; ++j) {
17 dp[i] = min(dp[i], 1 + dp[j]);
18 }
19 }
20
21 return dp[0] >= 1e9 ? -1 : dp[0];
22 }
23};
24
25int main() {
26 Solution sol;
27 vector<int> nums = {2, 3, 1, 1, 4};
28 cout << "Min Jumps: " << sol.jump(nums) << endl;
29 return 0;
30}

Time & Space Complexity

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

3. Greedy BFS / Range Window (O(n) Time, O(1) Space)

Intuition

Treat jumps as BFS depth levels. Track the farthest reachable index in the current jump window.

Algorithm

  1. Initialize jumps = 0, currentEnd = 0, farthest = 0.
  2. Loop i from 0 to n - 2:
  3. farthest = max(farthest, i + nums[i]).
  4. If i == currentEnd:
  5. jumps++.
  6. currentEnd = farthest.
  7. If currentEnd >= n - 1, break early.
  8. Return jumps.
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, farthest = 0;
14 for (int i = 0; i < n - 1; ++i) {
15 farthest = max(farthest, i + nums[i]);
16 if (i == currentEnd) {
17 jumps++;
18 currentEnd = farthest;
19 if (currentEnd >= n - 1) break;
20 }
21 }
22
23 return jumps;
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<int> nums = {2, 3, 1, 1, 4};
30 cout << "Min Jumps: " << sol.jump(nums) << endl;
31 return 0;
32}

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.Recursive BranchingO(k^n)O(n)Recursively test every jump step.Overlapping jump paths
2.1D Bottom-Up DPO(n^2)O(n)dp[i] = 1 + min(dp[j]) for reachable indices j.Inner loop scanning jump range
3.Greedy BFS WindowOptimalO(n)O(1)Maintain currentEnd and farthest reachable index per jump level.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Iterating up to index n - 1 and accidentally counting an extra jump.

Pitfall 2:

Failing to break early when currentEnd >= n - 1.

Crucial Edge Cases to Validate:

  • n = 1: Already at destination; returns 0 jumps.
  • nums[0] = 0 with n > 1: Cannot move forward; unreachable (if problem allows unreachable instances).
  • Direct jump to end from index 0: nums[0] >= n - 1; returns 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify that the problem is equivalent to finding the shortest path on an unweighted directed graph, which is why BFS / greedy range expansion runs in O(V + E) = O(n).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the loop in the greedy BFS approach iterate up to n - 2 instead of n - 1?

Back to DSA Sheet