Jump Game II: Minimum Jumps to Reach the End

98.6k
0

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.

Your goal is to reach the last index in the minimum number of jumps. You may assume that you can always safely reach the last index.

Example 1

Input: nums = [2, 3, 1, 1, 4]

Output: 2

Explanation:
Jump from index 0 to index 1, then jump from index 1 to the last index.

Example 2

Input: nums = [2, 3, 0, 1, 4]

Output: 2

Explanation:
Jump from index 0 to index 1, then jump from index 1 to index 4.

Brute Approach

From any index, there are many possible jumps. For example, if nums[i] = 3, then from index i we can try going to i + 1, i + 2, or i + 3.

A direct recursive solution would try all possible jump paths again and again. That creates repeated work because the same index can be reached from many previous indices.

So the useful observation is: If the minimum jumps needed from index i to the end is already known, there is no need to calculate it again. This is where memoization helps. Treat each index as a smaller subproblem:

dp[i] = minimum jumps needed to reach the last index from index i

For each index, try all reachable next indices, take the minimum answer among them, and store it.

Algorithm

  • Create a memo array where memo[i] stores the minimum jumps needed from index i to reach the last index. It starts with -1 because no subproblem has been solved yet.

  • If the current index is already at or beyond the last index, return 0. This means no more jumps are needed.

  • If memo[index] already has an answer, return it directly. This avoids solving the same index repeatedly.

  • Try every valid jump from the current index. For each next index, recursively calculate how many jumps are needed from there.

  • If a reachable next index gives a valid answer, add 1 for the current jump and minimize the answer.

  • Store the final answer in memo[index] before returning it, so future calls can reuse it.

Dry Run

Jump Game 2 Brute Dry Run

Jump Game 2 Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/*
Returns the minimum jumps needed from the given index
to reach the last index using recursion and memoization.
*/
int solve(int index, vector<int>& nums, vector<int>& memo) {
int n = nums.size();
// If the current index has reached the destination,
// no more jumps are needed.
if (index >= n - 1) {
return 0;
}
// If this index was already solved,
// reuse the stored answer.
if (memo[index] != -1) {
return memo[index];
}
// This stores the best answer found from this index.
int minJumps = INT_MAX;
// This prevents checking jumps beyond the array boundary.
int farthestJump = min(n - 1, index + nums[index]);
for (int nextIndex = index + 1; nextIndex <= farthestJump; nextIndex++) {
int nextJumps = solve(nextIndex, nums, memo);
// Use this path only if the next index can reach the end.
if (nextJumps != INT_MAX) {
minJumps = min(minJumps, 1 + nextJumps);
}
}
memo[index] = minJumps;
return memo[index];
}
public:
/*
Returns the minimum number of jumps needed
to reach the last index.
*/
int jump(vector<int>& nums) {
// Stores solved answers for each index.
vector<int> memo(nums.size(), -1);
return solve(0, nums, memo);
}
};
// Driver code starts
int main() {
vector<int> nums = {2, 3, 1, 1, 4};
Solution solution;
cout << solution.jump(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(n^2), because from each index, the algorithm may try many possible next jumps.

Space Complexity: O(n), because the memo array and recursion stack are used.

Optimal Approach

At any index, nums[i] gives a range of positions that can be reached. A common beginner mistake is thinking, “Always jump the maximum distance immediately.” But that is not always the safest thought.

Instead, think in ranges Suppose one jump lets us reach indices from 1 to 3. Before deciding the next jump count, check all positions in this range and ask:

“From any of these positions, what is the farthest index the next jump can reach?” This is like moving level by level. All indices reachable with 1 jump form one range. All indices reachable with 2 jumps form the next range.

So, every time the current range ends, one more jump is definitely needed. While scanning inside that range, keep updating the farthest next position. That gives the minimum jumps because each jump expands the reachable range as far as possible.

Algorithm

  • Keep jumps to count how many jumps have been taken. It starts from 0 because we begin at index 0.

  • Keep currentEnd, which marks the farthest index reachable using the current number of jumps. When the loop reaches this boundary, the current jump range is finished.

  • Keep farthest, which stores the farthest index reachable using one more jump from any index inside the current range. This helps choose the best next range without trying every path separately.

  • Traverse the array only up to the second-last index. Once the last index is reachable, there is no need to jump from it.

  • At each index, update farthest using i + nums[i]. This checks how far the next jump could go if this index is used.

  • If the current index reaches currentEnd, increase jumps because moving beyond this range needs one more jump. Then set currentEnd to farthest so the next range becomes active.

Key Points

  • If the array has only one element, the answer is 0 because the start is already the end.

Dry Run

Jump Game 2 Optimal Dry Run

Jump Game 2 Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the minimum number of jumps needed
to reach the last index using greedy ranges.
*/
int jump(vector<int>& nums) {
int n = nums.size();
// A single index is already the destination.
if (n <= 1) {
return 0;
}
// Stores how many jumps have been used so far.
int jumps = 0;
// Marks the end of the range covered by current jumps.
int currentEnd = 0;
// Stores the farthest index reachable from the current range.
int farthest = 0;
for (int i = 0; i < n - 1; i++) {
// Try to extend the next reachable range from this index.
farthest = max(farthest, i + nums[i]);
// When the current range ends, one more jump is needed.
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
// Once the last index is inside the range,
// no more scanning is needed.
if (currentEnd >= n - 1) {
break;
}
}
}
return jumps;
}
};
// Driver code starts
int main() {
vector<int> nums = {2, 3, 1, 1, 4};
Solution solution;
cout << solution.jump(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(n), because each index is visited once.

Space Complexity: O(1), because constant space is used.

Interview follow-up Questions

currentEnd is the boundary of the current jump range. When the loop reaches it, all positions reachable with the current number of jumps have been checked, so moving forward needs one more jump.

GreedyTwo PointerSortingArrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67.1k
Arrays

Search Element in Matrix

Input: mat = [[1, 2, 3], [7, 6, 8], [9, 2, 5]], X = 6 Output: {1, 1} Explanation: Target value 6 is present at row 1 and column 1 . Input: mat = [[3, 4, 5, 0], [2, 9, 8, 7]], X = 10 Output: {-1, -1...

98.4k
Comments0