Description:
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].
Examples:
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: 2Solution in Python:
To solve the problem of finding the minimum number of jumps needed to reach the end of the array, we can use a greedy algorithm.
Python
from typing import List
class Solution:
def jump(self, nums: List[int]) -> int:
# If the array length is 1, we are already at the end
if len(nums) == 1:
return 0
# Initialize the maximum reach, the end of the current jump, and the jump counter
max_reach = nums[0]
steps = nums[0]
jumps = 1
# Iterate through the array, except the last element
for i in range(1, len(nums)):
# If we have reached the end of the array, return the number of jumps
if i == len(nums) - 1:
return jumps
# Update the maximum reach
max_reach = max(max_reach, i + nums[i])
# Use a step to get to the current index
steps -= 1
# If no more steps left
if steps == 0:
# We must have used a jump
jumps += 1
# If we have used a jump, update the steps to the max reach from the current position
steps = max_reach - i
return jumpsDetailed Explanation:
- Base Case:
- If the length of
numsis 1, we are already at the last index, so return 0.
- If the length of
- Initialization:
max_reach: Tracks the farthest index we can reach so far.steps: The number of steps we can still take before we must make another jump.jumps: Counts the number of jumps we have made.
- Iteration:
- Iterate through the array starting from index 1 to
len(nums) - 1. - For each index
i:- Update
max_reachto be the maximum of its current value andi + nums[i], representing the farthest index we can reach from the current index. - Decrement
stepssince we used one step to get to indexi. - If
stepsbecomes zero, it means we need to make another jump:- Increment
jumps. - Update
stepsto be the distance we can cover with this new jump, which ismax_reach - i.
- Increment
- Update
- Iterate through the array starting from index 1 to
- Return Result:
- Return the number of jumps when we reach the end of the array.
This greedy approach ensures that we make the minimum number of jumps needed to reach the last index by always choosing the farthest reachable position within the current jump range.
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var jump = function(nums) {
if (nums.length <= 1) {
return 0; // No jumps needed if array length is 0 or 1
}
let jumps = 0;
let maxReach = 0;
let steps = 0;
for (let i = 0; i < nums.length - 1; i++) {
maxReach = Math.max(maxReach, i + nums[i]);
if (i === steps) {
jumps++;
if (maxReach >= nums.length - 1) {
return jumps; // If we can reach the end with the current jump
}
steps = maxReach; // Update steps to the new max reach
}
}
return jumps; // If we reach here, something went wrong because the problem guarantees we can reach the end
};Solution in Java:
Java
class Solution {
public int jump(int[] nums) {
if (nums.length <= 1) {
return 0; // No jumps needed if array length is 0 or 1
}
int jumps = 0;
int maxReach = 0; // Maximum index we can reach with the current number of jumps
int steps = 0; // Steps remaining in the current jump
for (int i = 0; i < nums.length - 1; i++) {
maxReach = Math.max(maxReach, i + nums[i]);
if (i == steps) {
jumps++;
if (maxReach >= nums.length - 1) {
return jumps; // If we can reach the end with the current jump
}
steps = maxReach; // Update steps to the new max reach
}
}
return jumps; // If we reach here, something went wrong because the problem guarantees we can reach the end
}
}Solution in C#:
C#
public class Solution {
public int Jump(int[] nums) {
if (nums.Length <= 1) {
return 0; // No jumps needed if array length is 0 or 1
}
int jumps = 0;
int maxReach = 0; // Maximum index we can reach with the current number of jumps
int steps = 0; // Steps remaining in the current jump
for (int i = 0; i < nums.Length - 1; i++) {
maxReach = Math.Max(maxReach, i + nums[i]);
if (i == steps) {
jumps++;
if (maxReach >= nums.Length - 1) {
return jumps; // If we can reach the end with the current jump
}
steps = maxReach; // Update steps to the new max reach
}
}
return jumps; // If we reach here, something went wrong because the problem guarantees we can reach the end
}
}