Problem Statement:
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Examples:
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation:
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation:
You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Constraints
1 <= nums.length <= 104
0 <= nums[i] <= 105
Time Complexity:
Time Complexity = O(n2)
Space Complexity:
Space Complexity = O(n)
Approach
- Start from
index 0and try all possible jumps from that position. - Use DFS recursion to check if we can reach the
last index. - From a position
start, try jumps from 1 to nums[start]. - If any jump leads to the last index (or a position that can reach it),
return true. - Use a
dp array(memoization) to store results for already visited indices to avoid recomputation. - If dp[start] is already computed,
return the stored value. - Store the
result(true or false) in dp[start] before returning.
Dry Run
Input: nums = [2, 3, 1, 1, 4]
Initialization: end = 4 dp = [-1, -1, -1, -1, -1] Step 1: Call dfs(0) start = 0 nums[0] = 2 → possible jumps = 1 or 2 Step 2: Try jump of 1 Call dfs(1) Step 3: dfs(1) nums[1] = 3 → possible jumps = 1, 2, 3 Step 4: Try jump of 1 Call dfs(2) Step 5: dfs(2) nums[2] = 1 → possible jump = 1 Step 6: Try jump of 1 Call dfs(3) Step 7: dfs(3) nums[3] = 1 → possible jump = 1 Step 8: Try jump of 1 Call dfs(4) Step 9: dfs(4) start === end → return true Step 10: Backtrack dfs(3) receives true dp[3] = true Step 11: Backtrack dfs(2) receives true dp[2] = true Step 12: Backtrack dfs(1) receives true dp[1] = true Step 13: Backtrack dfs(0) receives true dp[0] = true Final dp array: [true, true, true, true, -1]
Output: true
var canJump = function(nums) {
let end = nums.length - 1;
let dp = new Array(nums.length).fill(-1);
let dfs = (start) => {
if(start === end) return true;
if(dp[start] != -1) return dp[start];
let ans = false;
for(let i = 1; i <= nums[start] && !ans; i++){
if(start + i <= end){
ans = ans || dfs(start + i);
}
}
dp[start] = ans;
return ans;
}
return dfs(0);
};
class Solution:
def canJump(self, nums):
end = len(nums) - 1
dp = [-1] * len(nums)
def dfs(start):
if start == end:
return True
if dp[start] != -1:
return dp[start]
ans = False
for i in range(1, nums[start] + 1):
if not ans and start + i <= end:
ans = ans or dfs(start + i)
dp[start] = ans
return ans
return dfs(0)
class Solution {
public boolean dfs(int start, int[] nums, int[] dp) {
int end = nums.length - 1;
if(start == end) return true;
if(dp[start] != -1) return dp[start] == 1;
boolean ans = false;
for(int i = 1; i <= nums[start] && !ans; i++){
if(start + i <= end){
ans = ans || dfs(start + i, nums, dp);
}
}
dp[start] = ans ? 1 : 0;
return ans;
}
public boolean canJump(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, -1);
return dfs(0, nums, dp);
}
}
#include <iostream>
class Solution {
public:
bool dfs(int start, vector& nums, vector& dp) {
int end = nums.size() - 1;
if(start == end) return true;
if(dp[start] != -1) return dp[start];
bool ans = false;
for(int i = 1; i <= nums[start] && !ans; i++) {
if(start + i <= end) {
ans = ans || dfs(start + i, nums, dp);
}
}
dp[start] = ans;
return ans;
}
bool canJump(vector& nums) {
vector dp(nums.size(), -1);
return dfs(0, nums, dp);
}
};
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
bool dfs(int start, int* nums, int size, int* dp) {
int end = size - 1;
if(start == end)
return true;
if(dp[start] != -1)
return dp[start];
bool ans = false;
for(int i = 1; i <= nums[start] && !ans; i++) {
if(start + i <= end) {
ans = ans || dfs(start + i, nums, size, dp);
}
}
dp[start] = ans;
return ans;
}
bool canJump(int* nums, int numsSize) {
int* dp = (int*)malloc(numsSize * sizeof(int));
for(int i = 0; i < numsSize; i++)
dp[i] = -1;
bool result = dfs(0, nums, numsSize, dp);
free(dp);
return result;
}
public class Solution {
public bool Dfs(int start, int[] nums, int[] dp)
{
int end = nums.Length - 1;
if(start == end)
return true;
if(dp[start] != -1)
return dp[start] == 1;
bool ans = false;
for(int i = 1; i <= nums[start] && !ans; i++)
{
if(start + i <= end)
{
ans = ans || Dfs(start + i, nums, dp);
}
}
dp[start] = ans ? 1 : 0;
return ans;
}
public bool CanJump(int[] nums) {
int[] dp = new int[nums.Length];
Array.Fill(dp, -1);
return Dfs(0, nums, dp);
}
}
