Jump Game II Solution In C++/Java/Python/JS
Problem Description
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 nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
Example
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.
Input: nums = [2,3,0,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.
Constraints
- 1 <= nums.length <= 104
- 0 <= nums[i] <= 1000
- It's guaranteed that you can reach nums[n - 1].
Figuring out "Jump Game II" can be solved using different approaches. We will first figure out the most intuitive approach and move to the optimal approach if exists. Let's sit with a pen and paper and figure out the algorithm !!
Brute Force Approach
Intuition
We are given an array nums, where each element tells us the maximum number of steps we can jump forward. Our task is to reach the last index (nums[n-1]) in the fewest jumps possible.
To solve this, we explore all possible jump sequences and determine the minimum number of jumps required.
Let’s figure out how to solve this using an example:
nums = [2, 3, 1, 1, 4]
Starting Point (Index 0):
- The value at index 0 is 2, which means you can jump up to 2 steps forward.
- From index 0, you have two options: jump to index 1 or jump to index 2.
First Jump Options:
- Option 1: Jump to index 1
- The value at index 1 is 3, which means you can jump up to 3 steps forward.
- From index 1, you have three options: jump to index 2, jump to index 3, or jump to index 4.
- Option 2: Jump to index 2
- The value at index 2 is 1, which means you can jump up to 1 step forward.
- From index 2, you have one option: jump to index 3.
Second Jump Options from Index 1:
- Option 1: Jump to index 2
- The value at index 2 is 1, which means you can jump up to 1 step forward.
- From index 2, you have one option: jump to index 3.
- Option 2: Jump to index 3
- The value at index 3 is 1, which means you can jump up to 1 step forward.
- From index 3, you have one option: jump to index 4.
- Option 3: Jump to index 4
- Index 4 is the last index, so you have reached the end.
Second Jump Options from Index 2:
- Option 1: Jump to index 3
- The value at index 3 is 1, which means you can jump up to 1 step forward.
- From index 3, you have one option: jump to index 4.
Third Jump Options from Index 3:
- Option 1: Jump to index 4
- Index 4 is the last index, so you have reached the end.
Possible Paths Explored:
- Path 1: 0 → 1 → 2 → 3 → 4
- Jump from index 0 to 1, then to 2, then to 3, and finally to 4.
- Total Jumps: 3
- Path 2: 0 → 1 → 3 → 4
- Jump from index 0 to 1, then to 3, and finally to 4.
- Total Jumps: 2
- Path 3: 0 → 1 → 4
- Jump from index 0 to 1, and then directly to 4.
- Total Jumps: 2
- Path 4: 0 → 2 → 3 → 4
- Jump from index 0 to 2, then to 3, and finally to 4.
- Total Jumps: 3
Conclusion
Among these paths, Path 2 (0 → 1 → 3 → 4) and Path 3 (0 → 1 → 4) are the optimal paths with 2 jumps each. These paths demonstrate the minimum number of jumps required to reach the last index.
Let's now see how our algorithm looks!
Jump Game II Algorithm
- We set minJumps to infinity and start at index = 0.
- If we reach or exceed the last index, we return 0.
- We loop from 1 to nums[index] to explore all possible jumps.
- For each jump, we recursively find the minimum jumps needed from the new index.
- We update minJumps with the minimum of the current minJumps and the result of the recursive call plus one.
- Finally, we return minJumps after exploring all possible jumps.
Approach
Initialize Variables:
- minJumps = Infinity: Tracks the minimum number of jumps needed.
- index = 0: The starting index for the recursive calls.
Recursive Function:
- Base Case: If the current index is greater than or equal to the last index, return 0 (no more jumps needed).
- Loop Through Possible Jumps: Loop from i = 1 to nums[index] (all possible jumps from the current index).
- Recursive Call: For each possible jump, recursively call the function to find the minimum jumps needed from the new index (index + i).
- Update Minimum Jumps: If the recursive call returns a valid number of jumps (not Infinity), update minJumps to the minimum of the current minJumps and the jumps returned by the recursive call plus one (for the current jump).
Return the Minimum Jumps:
- Once all possible jumps are explored, return minJumps which contains the minimum jumps needed to reach the last index.
Dry-Run
Example input: nums = [2, 0, 1, 3, 0, 2]
Output: 3
Explanation
Recursive Calls and Steps
Step 1: Start at index = 0
- nums[0] = 2, so we can jump to: index 1 or index 2
Step 2: Jump to index = 1
- nums[1] = 0, so no forward jumps possible.
- This path fails.
Backtrack to index = 0 and try another jump.
Step 3: Jump to index = 2
- nums[2] = 1, so we can jump to: index 3
Step 4: Jump to index = 3
- nums[3] = 3, so we can jump to: index 4 or index 5
Step 5: Jump to index = 4
- nums[4] = 0, so no forward jumps possible.
- This path fails.
Backtrack to index = 3 and try another jump.
Step 6: Jump to index = 5
- index = 5 is the last index.
- Reached the goal!
Final Answer
The minimum jumps required = 3
(index 0) → (index 2) → (index 3) → (index 5)
Jump Game II Solution
Now let's checkout the "Jump Game II code" in C++, Java, Python and JavaScript.
"Jump Game II" Code in all Languages.
1. Jump Game II solution in C++ Try on Compiler
class Solution {
// Function to find the minimum jumps to reach the last index
int findMinJumps(vector<int>& nums, int index) {
// If we reach or exceed the last index, no more jumps are needed
if (index >= nums.size() - 1) return 0;
// Variable to store the minimum jumps needed
int minJumps = INT_MAX;
// Try all possible jumps from the current position
for (int i = 1; i <= nums[index]; i++) {
// Recursive call to calculate jumps from the new position
int currentJumps = findMinJumps(nums, index + i);
// Update minJumps only if a valid path exists
if (currentJumps != INT_MAX) {
minJumps = min(minJumps, currentJumps + 1);
}
}
return minJumps;
}
public:
// Main function to call the recursive function
int jump(vector<int>& nums) {
return findMinJumps(nums, 0);
}
};2. Jump Game II Solution in Java Try on Compiler
class Solution {
// Function to find the minimum jumps to reach the last index
private int findMinJumps(int[] nums, int index) {
// If we reach or exceed the last index, no more jumps are needed
if (index >= nums.length - 1) return 0;
// Variable to store the minimum jumps needed
int minJumps = Integer.MAX_VALUE;
// Try all possible jumps from the current position
for (int i = 1; i <= nums[index]; i++) {
// Recursive call to calculate jumps from the new position
int jumps = findMinJumps(nums, index + i);
// Update minJumps only if a valid path exists
if (jumps != Integer.MAX_VALUE) {
minJumps = Math.min(minJumps, jumps + 1);
}
}
return minJumps;
}
// Main function to call the recursive function
public int jump(int[] nums) {
return findMinJumps(nums, 0);
}
}3. Jump Game II Solution in Python Try on Compiler
class Solution:
# Function to find the minimum jumps to reach the last index
def minJumps(self, nums: List[int], index: int) -> int:
# If we reach or exceed the last index, no more jumps are needed
if index >= len(nums) - 1:
return 0
# Variable to store the minimum jumps needed
min_jumps = float('inf')
# Try all possible jumps from the current position
for i in range(1, nums[index] + 1):
# Recursive call to calculate jumps from the new position
jumps = self.minJumps(nums, index + i)
# Update min_jumps only if a valid path exists
if jumps != float('inf'):
min_jumps = min(min_jumps, jumps + 1)
return min_jumps
# Main function to call the recursive function
def jump(self, nums: List[int]) -> int:
return self.minJumps(nums, 0)4. Jump Game II solution in JavaScript Try on Compiler
/**
* Function to find the minimum jumps to reach the last index
* @param {number[]} nums
* @param {number} index
* @return {number}
*/
function findMinJumps(nums, index) {
// If we reach or exceed the last index, no more jumps are needed
if (index >= nums.length - 1) return 0;
// Variable to store the minimum jumps needed
let minJumps = Infinity;
// Try all possible jumps from the current position
for (let i = 1; i <= nums[index]; i++) {
// Recursive call to calculate jumps from the new position
let jumps = findMinJumps(nums, index + i);
// Update minJumps only if a valid path exists
if (jumps !== Infinity) {
minJumps = Math.min(minJumps, jumps + 1);
}
}
return minJumps;
}
/**
* @param {number[]} nums
* @return {number}
*/
function jump(nums) {
return findMinJumps(nums, 0);
}Jump Game II Complexity Analysis
Time Complexity: O(2ⁿ)
Recursive Calls:
- From each index i, we make at most nums[i] recursive calls.
- In the worst case, if nums[i] allows multiple jumps (e.g., nums = [1, 1, 1, ..., 1]), the recursion forms a tree-like structure where each index makes up to nums[i] recursive calls. Since each jump creates multiple branches.
- The number of recursive calls can grow exponentially, leading to O(2ⁿ) complexity in the worst case.
Thus, the time complexity is O(2ⁿ) (exponential).
Space Complexity: O(n)
Auxiliary Space for Recursion:
- The recursion depth is at most O(n) (in case of a worst-case scenario where all jumps are 1).
- No additional data structures are used apart from recursive calls.
Thus, the space complexity is O(n) due to recursive stack space.
This brute force approach takes exponential time complexity (O(2ⁿ)), which is highly inefficient. This approach will fail for large inputs. The interviewer will not be satisfied with this, so let's figure out an optimal solution.
Optimal Approach
Intuition
We have an array nums, where each element tells us how far we can jump forward from that position. Starting from index 0, we must reach the last index (nums[n-1]) in the fewest jumps possible.
Let’s figure out how to solve this using an example:
nums = [2, 1, 3, 0, 1, 2, 3]
Our goal is to reach the last index (6) in the minimum number of jumps.
Step-by-step Thought Process:
- Start at index 0 (value = 2):
- We can jump 1 step to index 1 or 2 steps to index 2.
- Which one should we pick? Let’s look at both options.
- Check index 1 (value = 1):
- From here, we can only move 1 step to index 2, which is already reachable from index 0.
- This means jumping to index 1 does not help much.
- Check index 2 (value = 3):
- From here, we can jump up to 3 steps, reaching index 3, 4, or 5.
- The farther we go, the closer we get to the goal.
- The best choice is: jump to index 2 directly from 0.
- Explore Index 2 (value = 3):
- From index 2, we can jump up to 3 steps, reaching index 3 (value = 0), Index 4 (value = 1), Index 5 (value = 2)
- Which one should we pick? Let’s figure it out.
- Check index 3 (value = 0): Since index 3 has value 0, it doesn't help us move forward.
- Check index 4 (value = 1):
- From here, we can only move 1 step to index 5, which is already reachable from index 2.
- This means jumping to index 1 does not help much.
- Check index 5 (value = 2):
- Index 5 allows 2 steps, reaching index 6 (goal).
- Best choice: Jump from index 2 to 5 directly.
- Explore Index 5 (value = 2): From index 5, we can jump up to 2 steps, but with just 1 step, we can already reach index 6 (goal reached).
Thus, the minimum jumps required to reach the last index (6) are:
- Jump from index 0 → 2
- Jump from index 2 → 5
- Jump from index 5 → 6
Final Answer: Minimum jumps = 3
So, What Are We Actually Doing?
From this example, we realize:
- We always choose the position that lets us reach the farthest index in the fewest moves.
- We only increase our jump count when we must move beyond our current jump range.
Well summarized! Now, if you think about it, what kind of approach are we using here?
We are making the best possible choice at each step without looking ahead too much. This sounds like a greedy algorithm!
Exactly! The greedy approach works perfectly here because, at each step, we maximize our reach by updating the farthest index we can get to, without needing to explore all possible paths exhaustively.
Jump Game II Algorithm
- We initialize jumps = 0, farthest = 0, and currentEnd = 0.
- We iterate through the array (excluding the last element).
→ We update farthest to track the farthest position we can reach.
→ If we reach currentEnd, we take a jump, increase jumps, and update currentEnd to farthest. - Finally, we return jumps, which represents the minimum jumps needed to reach the last index.
Approach
Initialize Variables:
- jumps = 0: Tracks the number of jumps needed.
- farthest = 0: Keeps track of the farthest index reachable so far.
- currentEnd = 0: Marks the end of the current jump range.
Iterate Through Array: Loop from i = 0 to nums.length - 2 (excluding the last element).
Update Farthest Reachable Index: farthest = Math.max(farthest, i + nums[i]): Updates farthest to the maximum index reachable from the current position.
Check if End of Current Jump is Reached: If i == currentEnd: Increment jumps (because a new jump is needed) and update currentEnd = farthest (move to the farthest point found).
Return the Total Jumps: Once the loop completes, jumps contains the minimum jumps needed to reach the last index.
Let us understand this with a video,
Dry-Run
Example Input: nums = [3, 4, 2, 1, 2, 3, 1, 1]
Output: 3
Explanation
Initialization:
- jumps = 0 → Number of jumps taken
- farthest = 0 → Farthest index we can reach
- currentEnd = 0 → End of the current jump range
- At index 0 (nums[0] = 3)
- farthest = max(0, 0 + 3) = 3 (We can reach index 3)
- Reached currentEnd (0), so we must jump:
→ jumps = 1
→ currentEnd = 3
- At index 1 (nums[1] = 4)
- farthest = max(3, 1 + 4) = 5 (We can reach index 5)
- Not at currentEnd, so we continue.
- At index 2 (nums[2] = 2)
- farthest = max(5, 2 + 2) = 5 (No change)
- Not at currentEnd, so we continue.
- At index 3 (nums[3] = 1)
- farthest = max(5, 3 + 1) = 5 (No change)
- Reached currentEnd (3), so we must jump:
→ jumps = 2
→ currentEnd = 5
- At index 4 (nums[4] = 2)
- farthest = max(5, 4 + 2) = 6 (We can reach index 6)
- Not at currentEnd, so we continue.
- At index 5 (nums[5] = 3)
- farthest = max(6, 5 + 3) = 8 (We can reach index 8, which is beyond the last index)
- Reached currentEnd (5), so we must jump:
→ jumps = 3
→ currentEnd = 8
Since currentEnd has reached or exceeded the last index, we stop here.
Final Answer: 3
Jump Game II Solution
Now let's checkout the "Jump Game II code" in C++, Java, Python and JavaScript.
"Jump Game II" Code in all Languages.
1. Jump Game II solution in C++ Try on Compiler
class Solution {
public:
int jump(vector<int>& nums) {
// If there is only one element, no jumps are needed
if (nums.size() == 1) return 0;
// Tracks the number of jumps needed
int jumps = 0;
// Keeps track of the farthest index reachable so far
int farthest = 0;
// Marks the end of the current jump range
int currentEnd = 0;
// Iterate through the array (excluding the last element)
for (int i = 0; i < nums.size() - 1; i++) {
// Update farthest to track the maximum index reachable from the current position
farthest = max(farthest, i + nums[i]);
// If we reach the end of the current jump range
if (i == currentEnd) {
// Increase jump count as a new jump is needed
jumps++;
// Update currentEnd to the farthest point found
currentEnd = farthest;
// If we can already reach the last index, stop early
if (currentEnd >= nums.size() - 1) break;
}
}
// Return the minimum number of jumps needed
return jumps;
}
};2. Jump Game II Solution in Java Try on Compiler
class Solution {
public int jump(int[] nums) {
// If there is only one element, no jumps are needed
if (nums.length == 1) return 0;
// Tracks the number of jumps needed
int jumps = 0;
// Keeps track of the farthest index reachable so far
int farthest = 0;
// Marks the end of the current jump range
int currentEnd = 0;
// Iterate through the array (excluding the last element)
for (int i = 0; i < nums.length - 1; i++) {
// Update farthest to track the maximum index reachable from the current position
farthest = Math.max(farthest, i + nums[i]);
// If we reach the end of the current jump range
if (i == currentEnd) {
// Increase jump count as a new jump is needed
jumps++;
// Update currentEnd to the farthest point found
currentEnd = farthest;
// If we can already reach the last index, stop early
if (currentEnd >= nums.length - 1) break;
}
}
// Return the minimum number of jumps needed
return jumps;
}
}3. Jump Game II Solution in Python Try on Compiler
class Solution:
def jump(self, nums: List[int]) -> int:
# If there is only one element, no jumps are needed
if len(nums) == 1:
return 0
# Tracks the number of jumps needed
jumps = 0
# Keeps track of the farthest index reachable so far
farthest = 0
# Marks the end of the current jump range
currentEnd = 0
# Iterate through the array (excluding the last element)
for i in range(len(nums) - 1):
# Update farthest to track the maximum index reachable from the current position
farthest = max(farthest, i + nums[i])
# If we reach the end of the current jump range
if i == currentEnd:
# Increase jump count as a new jump is needed
jumps += 1
# Update currentEnd to the farthest point found
currentEnd = farthest
# If we can already reach the last index, stop early
if currentEnd >= len(nums) - 1:
break
# Return the minimum number of jumps needed
return jumps4. Jump Game II solution in JavaScript Try on Compiler
/**
* @param {number[]} nums
* @return {number}
*/
var jump = function(nums) {
// If there is only one element, no jumps are needed
if (nums.length === 1) return 0;
// Tracks the number of jumps needed
let jumps = 0;
// Keeps track of the farthest index reachable so far
let farthest = 0;
// Marks the end of the current jump range
let currentEnd = 0;
// Iterate through the array (excluding the last element)
for (let i = 0; i < nums.length - 1; i++) {
// Update farthest to track the maximum index reachable from the current position
farthest = Math.max(farthest, i + nums[i]);
// If we reach the end of the current jump range
if (i === currentEnd) {
// Increase jump count as a new jump is needed
jumps++;
// Update currentEnd to the farthest point found
currentEnd = farthest;
// If we can already reach the last index, stop early
if (currentEnd >= nums.length - 1) break;
}
}
// Return the minimum number of jumps needed
return jumps;
};Jump Game II Complexity Analysis
Time Complexity: O(n)
Iterating through the array while maintaining farthest:
- We traverse the array once, updating farthest at each step.
- This operation takes O(n) time.
Updating currentEnd and counting jumps:
- Each index is processed in constant time when a jump is required.
- This also takes O(n) time in the worst case.
Thus, the total time complexity is, O(n)
Space Complexity: O(1)
Auxiliary Space Complexity:
- The algorithm only uses a few extra variables (jumps, farthest, currentEnd).
- No additional data structures are used.
- Thus, auxiliary space complexity is O(1).
Total Space Complexity:
- Input storage (array of size n): O(n)
- In-place iteration → No extra space
- Variables (constant space) → O(1)
Thus, the total space complexity is O(1)
Similar Problems
Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach any index with value 0.
Notice that you can not jump outside of the array at any time.
You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0, which is equal to '0'. You can move from index i to index j if the following conditions are fulfilled:
- i + minJump <= j <= min(i + maxJump, s.length - 1), and
- s[j] == '0'.
Return true if you can reach index s.length - 1 in s, or false otherwise.