Jump Game 2 - Get min jumps
MediumUpdated: Aug 6, 2025
Practice on:
Problem
Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
Each element in the array 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.
Examples
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
This is an extension of [Jump Game 1 - Check if it reaches last index](jump-game-1-check-if-it-reaches-last-index)
Similar Problems
[Jump Game 1 - Check if it reaches last index](jump-game-1-check-if-it-reaches-last-index) [Jump Game 3](jump-game-3) [Jump Game 4](jump-game-4) [Jump Game 5](jump-game-5) [Jump Game 6](jump-game-6) [Jump Game 7](jump-game-7) [Minimum jumps to reduce number to 1](minimum-jumps-to-reduce-number-to-1)
Solution
We have already seen [Jump Game 1 - Check if it reaches last index](jump-game-1-check-if-it-reaches-last-index). We have a DP solution, but greedy solution is optimal with O(n).
Method 1 - Recursion
The problem can be solved using recursion by trying out each possible jump at each position and recursively calculating the minimum jumps required:
- Start from index 0 and explore each possible jump based on the current value.
- For each jump, recurse and calculate the minimum jumps required from the new index.
- Use base cases to minimize recursion:
- If the start index is the same as the end index, return 0 (no more jumps needed).
- If the value at the start index is 0, return
Integer.MAX_VALUE(can't move further). - If the remaining length can be covered in one jump, return 1.
Code
Java
public class Solution {
public int jump(int[] nums, int startIndex) {
// If reached the end, return 0
if (startIndex == nums.length - 1) {
return 0;
}
int size = nums.length;
int remainingLength = size - startIndex;
// If the remaining length can be covered in one jump, return 1
if (remainingLength <= nums[startIndex]) {
return 1;
}
// If current position is zero, can't move further
if (nums[startIndex] == 0) {
System.out.println("Cannot move further");
return Integer.MAX_VALUE;
}
int jumps = Integer.MAX_VALUE;
// Try every jump length from 1 to nums[startIndex]
for (int i = 1; i <= nums[startIndex]; i++) {
int temp = jump(nums, startIndex + i);
if (temp != Integer.MAX_VALUE) {
jumps = Math.min(jumps, 1 + temp);
}
}
return jumps;
}
}
Python
class Solution:
def jump(self, nums: List[int], start: int) -> int:
# If reached the end, return 0
if start == len(nums) - 1:
return 0
size = len(nums)
remaining_length = size - start
# If remaining length can be covered in one jump, return 1
if remaining_length <= nums[start]:
return 1
# If current position is zero, can't move further
if nums[start] == 0:
print("Cannot move further")
return float('inf')
jumps = float('inf')
# Try every jump length from 1 to nums[start]
for i in range(1, nums[start] + 1):
temp = self.jump(nums, start + i)
if temp != float('inf'):
jumps = min(jumps, 1 + temp)
return jumps
Complexity
- ⏰ Time complexity:
O(2^n), wherenis the length of the array in the worst case, due to exponential growth from each recursive call. - 🧺 Space complexity:
O(n), due to the maximum depth of the recursion stack.
Method 2 - Using Top Down Dynamic Programming
We observe that many subproblems are solved multiple times in the purely recursive approach. By using dynamic programming and memoization, we can store the results of these subproblems and use the stored results instead of recomputing them, thereby optimizing our solution.
Code
Java
public class Solution {
HashMap<Integer, Integer> memo = new HashMap<>();
private int jump(int[] nums, int startIndex) {
// If reached the end, return 0
if (startIndex == nums.length - 1) {
return 0;
}
// If the result is already computed, use it
if (memo.containsKey(startIndex)) {
return memo.get(startIndex);
}
int size = nums.length;
int remainingLength = size - startIndex;
// If remaining length can be covered in one jump, return 1
if (remainingLength <= nums[startIndex]) {
return 1;
}
// If current position is zero, can't move further
if (nums[startIndex] == 0) {
return Integer.MAX_VALUE;
}
int jumps = Integer.MAX_VALUE;
// Try every jump length from 1 to nums[startIndex]
for (int i = 1; i <= nums[startIndex]; i++) {
int temp = jump(nums, startIndex + i);
if (temp != Integer.MAX_VALUE) {
jumps = Math.min(jumps, 1 + temp);
}
}
memo.put(startIndex, jumps);
return jumps;
}
}
Python
class Solution:
def __init__(self):
self.memo: Dict[int, int] = {}
def jump(self, nums: List[int], start: int = 0) -> int:
# If reached the end, return 0
if start == len(nums) - 1:
return 0
# If the result is already computed, use it
if start in self.memo:
return self.memo[start]
size = len(nums)
remaining_length = size - start
# If remaining length can be covered in one jump, return 1
if remaining_length <= nums[start]:
return 1
# If current position is zero, can't move further
if nums[start] == 0:
return float('inf')
jumps = float('inf')
# Try every jump length from 1 to nums[start]
for i in range(1, nums[start] + 1):
temp = self.jump(nums, start + i)
if temp != float('inf'):
jumps = min(jumps, 1 + temp)
self.memo[start] = jumps
return jumps
Method 3 - Greedy Using BFS
The solution is based on a greedy approach where we track the maximum steps of the last jump:
- For each position, we calculate the farthest point that can be reached.
- The main idea is to keep track of the range of the current jump
[curBegin, curEnd]and the farthest pointcurFarthestthat all points in[curBegin, curEnd]can reach. - Once the current index reaches
curEnd, trigger another jump, and setcurEndtocurFarthest. Continue this process until we either reach the end of the array or determine that it's impossible.
Approach
- Initialize: Start with the first index. Track the current jump range
[curBegin, curEnd]and the farthest index that all points in this range can reach (curFarthest). - Iterate: Traverse the array and for each index, update
curFarthest. - Trigger Jumps: When the current index reaches
curEnd, increment the jump count and setcurEndtocurFarthest. - End Check: If
curEndreaches or exceeds the last index, return the number of jumps.
Code
Java
public class Solution {
public int jump(int[] nums) {
if (nums.length <= 1) {
return 0;
}
int jumps = 0;
int curEnd = 0;
int curFarthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
curFarthest = Math.max(curFarthest, i + nums[i]);
if (i == curEnd) {
jumps++;
curEnd = curFarthest;
if (curEnd >= nums.length - 1) {
break;
}
}
}
return jumps;
}
}
Python
class Solution:
def jump(self, nums: List[int]) -> int:
if len(nums) <= 1:
return 0
jumps: int = 0
cur_end: int = 0
cur_farthest: int = 0
for i in range(len(nums) - 1):
cur_farthest = max(cur_farthest, i + nums[i])
if i == cur_end:
jumps += 1
cur_end = cur_farthest
if cur_end >= len(nums) - 1:
break
return jumps
Complexity
- ⏰ Time complexity:
O(n), wherenis the length of the array. - 🧺 Space complexity:
O(1), as we use a constant amount of extra space.