🎨Now live: Try our Free AI Image Generation Feature

Intuition
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.
Approach
- Initialize two variables:
maxReach
to keep track of the farthest index we can reach, andtarget
to store the last index of the array. - Iterate through the array using an index
idx
: - For each position, updatemaxReach
to be the maximum ofmaxReach
andidx + nums[idx]
. - IfmaxReach
is greater than or equal totarget
, returntrue
because we can reach or exceed the last index. - IfmaxReach
is less than or equal to the current index and the current value ofnums[idx]
is 0, returnfalse
because we are stuck and cannot move forward. - If the loop completes without returning, it means
maxReach
was never able to reach thetarget
, so returnfalse
.
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:
bool canJump(vector& nums) {
int n = nums.size();
vector dp(n, 0);
dp[0] = 1;
for(int i=0; i
Python
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]
Java
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];
}
}
JavaScript
/**
* @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;
};