In this guide we will provide 45. Jump Game II LeetCode Solution with best time and space complexity. The solution to Jump Game II problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.
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 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 <= 104
0 <= nums[i] <= 1000
It's guaranteed that you can reach nums[n – 1].
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
45. Jump Game II LeetCode Solution in C++
class Solution {
public:
int jump(vector<int>& nums) {
int ans = 0;
int end = 0;
int farthest = 0;
// Start an 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;
}
}; /* code provided by PROGIEZ */
45. Jump Game II LeetCode Solution in Java
class Solution {
public int jump(int[] nums) {
int ans = 0;
int end = 0;
int farthest = 0;
// Start an 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;
}
} // code provided by PROGIEZ
45. Jump Game II LeetCode Solution in Python
class Solution:
def jump(self, nums: list[int]) -> int:
ans = 0
end = 0
farthest = 0
# Start an 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 #code by PROGIEZ
