Algorithm
Problem Name: 45. Jump Game II
Problem Link: https://leetcode.com/problems/jump-game-ii/
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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int jump(vector<int>& nums) {
int minJump = nums.size();
DFS(nums, 0, 0, minJump);
return minJump;
}
void DFS(vector<int>& nums, int pos, int jump, int& minJump){
if(pos == nums.size() - 1){
minJump = min(minJump, jump);
return;
}
int next = pos + 1, maxlen = 1 + nums[pos + 1];
for(int i = 1; i <= nums[pos] && pos + i < nums.size(); i++>
if(i + nums[pos + i] > maxlen || pos + i == nums.size() - 1) next = pos + i, maxlen = i + nums[next];
DFS(nums, next, jump + 1, minJump);
}
};
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const jump = function(nums) {
if (nums.length <= 1) return 0;
let curMax = 0; // to mark the last element in a level
let level = 0, i = 0;
while (i < = curMax) {
let furthest = curMax; // to mark the last element in the next level
for (; i < = curMax; i++) {
furthest = Math.max(furthest, nums[i] + i);
if (furthest >= nums.length - 1) return level + 1;
}
level++;
curMax = furthest;
}
return -1; // if i < curMax, i can't move forward anymore (the last element in the array can't be reached)
};
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def jump(self, nums):
last = cur = jump = i = 0
while cur < len(nums) - 1:
while i <= last:
if i + nums[i] > cur: cur = i + nums[i]
i += 1
last = cur
jump += 1
return jump
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _045_JumpGame2
{
public int Jump(int[] nums)
{
int maxRight = 0, currentRight = 0, count = 0;
for (int i = 0; i < nums.Length; i++)
{
if (i > maxRight) { return 0; }
if (i > currentRight)
{
count++;
currentRight = maxRight;
}
if (i + nums[i] > maxRight) { maxRight = i + nums[i]; }
}
return count;
}
}
}
Input
Output