In this post, we are going 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.
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
Now, let’s see the leetcode solution of Jump Game II Leetcode Solution.
Jump Game II Leetcode Solution 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 Solution 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 Solution 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 Chase2learn This tutorial is only for Educational and Learning purposes.
