🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires finding the minimum number of jumps needed to reach the last index of the array. Each element in the array represents the maximum jump length from that position. To solve this problem, we need to keep track of the farthest point that can be reached with the current number of jumps and determine when to make a jump to extend our reach.
Approach
- Initialize three variables:
-
currentReach
to keep track of the farthest index that can be reached with the current number of jumps, -currentMax
to store the farthest index that can be reached in the next jump, -jumps
to count the number of jumps made. - Iterate through the array up to the second last element:
- For each position, update
currentMax
to be the maximum ofcurrentMax
andi + nums[i]
. - If the current indexi
is equal tocurrentReach
, incrementjumps
and updatecurrentReach
tocurrentMax
. - Return the number of jumps.
Complexity
Time Complexity
The time complexity is O(n), where n
is the length of the array. This is because we iterate through the array once.
Space Complexity
The space complexity is O(1) since we are only using a few extra variables that do not scale with the input size.
Code
C++
class Solution {
public:
int jump(vector& nums) {
int n = nums.size();
if (n == 1) return 0;
int currentReach = 0;
int currentMax = 0;
int jumps = 0;
for (int i = 0; i < n - 1; ++i) {
if (i + nums[i] > currentMax) {
currentMax = i + nums[i];
}
if (i == currentReach) {
++jumps;
currentReach = currentMax;
}
}
return jumps;
}
};
Python
class Solution:
def jump(self, nums: List[int]) -> int:
dp = [10 ** 100] * len(nums)
dp[0] = 0
for i in range (len(nums)):
num = nums[i]
stop = min(i + num + 1, len(nums))
for j in range(1, stop - i):
dp[i + j] = min(dp[i + j], dp[i] + 1)
return dp[-1]
Java
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[n - 1] = 0;
for (int i = n - 2; i >= 0; i--) {
int min = Integer.MAX_VALUE;
for (int j = 1; j <= nums[i] && i + j < n; j++) {
min = Math.min(min, dp[i + j]);
}
dp[i] = min == Integer.MAX_VALUE ? min : min + 1;
}
return dp[0];
}
}
JavaScript
var jump = function(nums) {
let n = nums.length;
if(n == 1) return 0;
let currentReach = 0;
let currentMax = 0;
let jump = 0;
for(let i =0; i < n-1; i++){
if(i+nums[i] > currentMax){
currentMax = i + nums[i];}
if(i == currentReach){
jump++;
currentReach = currentMax;
console.log(i, jump, currentReach)
}}
return jump;
};