In this post, you will know how to solve the Jump Game II Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.
Problem
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]andi + 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 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 <= 1040 <= nums[i] <= 1000
Jump Game II Leetcode Solutions in Python
class Solution:
def jump(self, nums: List[int]) -> int:
ans = 0
end = 0
farthest = 0
# Implicit BFS
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if farthest >= len(nums) - 1:
ans += 1
break
if i == end: # Visited all the items on the current level
ans += 1 # Increment the level
end = farthest # Make the queue size for the next level
return ans
Jump Game II Leetcode Solutions in CPP
class Solution {
public:
int jump(vector<int>& nums) {
int ans = 0;
int end = 0;
int farthest = 0;
// Implicit BFS
for (int i = 0; i < nums.size() - 1; ++i) {
farthest = max(farthest, i + nums[i]);
if (farthest >= nums.size() - 1) {
++ans;
break;
}
if (i == end) { // Visited all the items on the current level
++ans; // Increment the level
end = farthest; // Make the queue size for the next level
}
}
return ans;
}
};
Jump Game II Leetcode Solutions in Java
class Solution {
public int jump(int[] nums) {
int ans = 0;
int end = 0;
int farthest = 0;
// Implicit BFS
for (int i = 0; i < nums.length - 1; ++i) {
farthest = Math.max(farthest, i + nums[i]);
if (farthest >= nums.length - 1) {
++ans;
break;
}
if (i == end) { // Visited all the items on the current level
++ans; // Increment the level
end = farthest; // Make the queue size for the next level
}
}
return ans;
}
}
Note: This problem Jump Game II is generated by Leetcode but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.
Next: Remove Duplicates from Sorted Array II Leetcode Solution
