Jump Game II — LeetCode #45
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 <= 104
0 <= nums[i] <= 1000
Solutions:
Python
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0
max_reach, steps, end = 0, 0, 0
for i in range(n - 1):
max_reach = max(max_reach, i + nums[i])
if i == end:
end = max_reach
steps += 1
return steps
C#
public class Solution {
public int Jump(int[] nums) {
int n = nums.Length;
if (n < 2) {
return 0;
}
int maxReach = 0, steps = 0, end = 0;
for (int i = 0; i < n - 1; i++) {
maxReach = Math.Max(maxReach, i + nums[i]);
if (i == end) {
end = maxReach;
steps++;
}
}
return steps;
}
}
Java
class Solution {
public int jump(int[] nums) {
int n = nums.length;
if (n < 2) {
return 0;
}
int maxReach = 0, steps = 0, end = 0;
for (int i = 0; i < n - 1; i++) {
maxReach = Math.max(maxReach, i + nums[i]);
if (i == end) {
end = maxReach;
steps++;
}
}
return steps;
}
}
Javascript
/**
* @param {number[]} nums
* @return {number}
*/
var jump = function(nums) {
let n = nums.length;
if (n < 2) {
return 0;
}
let maxReach = 0, steps = 0, end = 0;
for (let i = 0; i < n - 1; i++) {
maxReach = Math.max(maxReach, i + nums[i]);
if (i === end) {
end = maxReach;
steps++;
}
}
return steps;
};
Typescript
function jump(nums: number[]): number {
let n = nums.length;
if (n < 2) {
return 0;
}
let maxReach = 0, steps = 0, end = 0;
for (let i = 0; i < n - 1; i++) {
maxReach = Math.max(maxReach, i + nums[i]);
if (i === end) {
end = maxReach;
steps++;
}
}
return steps;
}
PHP
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function jump($nums) {
$n = count($nums);
if ($n < 2) {
return 0;
}
$maxReach = 0;
$steps = 0;
$end = 0;
for ($i = 0; $i < $n - 1; $i++) {
$maxReach = max($maxReach, $i + $nums[$i]);
if ($i === $end) {
$end = $maxReach;
$steps++;
}
}
return $steps;
}
}
I hope this helps! Let me know if you have any questions. Don’t forget to follow and give some claps to support my content