Dare2Solve
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.
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.currentMax
to be the maximum of currentMax
and i + nums[i]
.i
is equal to currentReach
, increment jumps
and update currentReach
to currentMax
.The time complexity is O(n), where n
is the length of the array. This is because we iterate through the array once.
The space complexity is O(1) since we are only using a few extra variables that do not scale with the input size.
class Solution {
public:
int jump(vector<int>& 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;
}
};
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]
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];
}
}
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;
};