Dare2Solve
The problem requires determining whether it is possible to reach the last index of the array starting from the first index. Each element in the array represents the maximum number of steps that can be jumped forward from that element. To solve this problem, we need to keep track of the farthest point that can be reached as we iterate through the array.
maxReach
to keep track of the farthest index we can reach, and target
to store the last index of the array.idx
:
maxReach
to be the maximum of maxReach
and idx + nums[idx]
.maxReach
is greater than or equal to target
, return true
because we can reach or exceed the last index.maxReach
is less than or equal to the current index and the current value of nums[idx]
is 0, return false
because we are stuck and cannot move forward.maxReach
was never able to reach the target
, so return false
.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:
bool canJump(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 0);
dp[0] = 1;
for(int i=0; i<n; ++i){
if(dp[i] == 1){
int maxjump = min(n-1, i + nums[i]);
for(int j=i+1; j<=maxjump; ++j){
dp[j] = 1;
}
}
}
return dp[n-1] == 1;
}
};
class Solution:
def canJump(self, nums: List[int]) -> bool:
reachable = [False for i in range(len(nums))]
reachable[0]=True
for i in range(len(nums)):
if not reachable[i]:
continue
for j in range(i+1, i+nums[i]+1):
if j >= len(nums):
return True
else:
reachable[j]=True
return reachable[len(nums)-1]
class Solution {
public boolean canJump(int[] nums) {
boolean[] dp = new boolean[nums.length];
dp[nums.length - 1] = true;
for (int i = dp.length - 1; i >= 0; i--) {
if (dp[i]) {
for (int j = 0; j < i; j++) {
if (nums[j] >= i - j) {
dp[j] = true;
if (dp[0])
return true;
}
}
}
}
return dp[0];
}
}
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function (nums) {
let idx = 0;
let max = 0;
let target = nums.length - 1;
while (idx < nums.length) {
max = Math.max(max, idx + nums[idx]);
console.log(max, idx)
if (max >= target) {
return true;
}
if (max <= idx && nums[idx] === 0) {
return false;
}
idx++;
}
return false;
};