Problem
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.
OR
Write a function to determine whether a person can reach the other end of the array if he starts at index 0 and if they cannot hop more than the value contained at that index.
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.
Follow up
Solution
Method 1 - Brute Force Using Recursion
We can start from index 0, and keep on jumping, till we reach out goal or point of failure.
Time complexity - O(n^n). At each step, we can take 1..n steps.
Method 2 - DP
We can look at the decision tree above, we see repetitive problems. We can use cache dp[] as boolean array, to see if we already solved that problem. If the step is true, then previous step can also be true, if it part of the array.
Method 3 - Greedy - Starting from Start
We can solve this problem using a greedy approach by tracking the maximum index that can be reached. The key is to determine:
- When the current position cannot reach the next position (
return false). - When the maximum index can reach the end (
return true).
The largest index that can be reached is calculated as: i + nums[i].
$$ \begin{array}{c|c|c|c|c|c} \text{index} & 0 & 1 & 2 & 3 & 4 \\ \hline \text{nums} & 3 & 2 & 1 & 0 & 4 \\ \hline \text{max} & 3 & 3 & 3 & \colorbox{red} X & - \\ \end{array} $$
Code
Java
public class Solution {
public boolean canJump(int[] nums) {
int maxReach = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
if (i > maxReach) {
return false;
}
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= n - 1) {
return true;
}
}
return false;
}
}
Python
class Solution:
def canJump(self, nums: List[int]) -> bool:
max_reach: int = 0
n: int = len(nums)
for i in range(n):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])
if max_reach >= n - 1:
return True
return False
Rust
Gotchas: i is of type usize which is not compatible with i32 so have to typecast nums[i] while adding to i. Second, changed initial value of coverage to 0 instead of nums[0] again because of typecasting.
use std::cmp;
pub fn can_jump(nums: Vec<i32>) -> bool {
if nums.len() <= 1 { return true; }
let n = nums.len();
let mut coverage = 0;
for i in 0..n {
if coverage < i {
return false;
}
coverage = cmp::max(coverage, i + nums[i] as usize);
if (coverage >= n) {
return true;
}
}
return true;
}
Complexity
- ⏰ Time complexity:
O(n), wherenis the length of the array, since we iterate through the array once. - 🧺 Space complexity:
O(1), as we use a constant amount of extra space.
Method 4 - Greedy - Starting from end
We can solve this problem by starting from the end of the array and moving to the left. Suppose m is the last index. If we can reach from m-1 to m, we can shift the goal post from m to m-1 and continue. Essentially, if we find that the current position can reach the goal (i.e., the last index), we move the goal to this current position and repeat the process until we either reach the start of the array or determine that it’s impossible.
$$ \begin{array}{c|c|c|c|c|c} \text{Index} & 0 & 1 & 2 & 3 & 4 \\ \hline \text{nums} & 3 & 2 & 1 & 0 & 4 \\ \hline \text{Goal Post} & & & & 3 & 4 \\ \hline \text{Goal Post} & & & 3 & 3 & 4 \\ \hline \text{Goal Post} & & 3 & 3 & 3 & 4 \\ \hline \text{Goal Post} & 3 & 3 & 3 & 3 & 4 \\ \end{array} $$
Approach
- Initialize the goal to be the last index.
- Iterate through the array from right to left.
- For each position, check if it can reach the current goal.
- If it can, update the goal to the current position.
- At the end, check if the goal has reached the first index.
Code
Java
public class Solution {
public boolean canJump(int[] nums) {
int goal = nums.length - 1;
for (int i = nums.length - 2; i >= 0; i--) {
//we cannot recover now, as we already have lost the momentum
if (i + nums[i] >= goal) {
goal = i;
}
}
return goal == 0; // goal will be more than 0, when we cannot reach end
}
}
Python
class Solution:
def canJump(self, nums: List[int]) -> bool:
goal: int = len(nums) - 1
for i in range(len(nums) - 2, -1, -1):
if i + nums[i] >= goal:
goal = i
return goal == 0
Complexity
- ⏰ Time complexity:
O(n), wherenis the length of the array, since we iterate through the array once. - 🧺 Space complexity:
O(1), as we use a constant amount of extra space.
Method 5 - Greedy - kind of 2 pointers
Focus on the current position (curr) and keep updating the furthest position (right) that can be reached. This approach ensures that you are always aware of the maximum index you can jump to, and you can confidently determine if the end of the array is reachable.
As we move through the array, we update right each time we find that we can reach further from the current index. If right becomes greater than or equal to the length of the array, it means we can reach the end, so we return true. If we exhaust the while loop without reaching the end, we return false.
Code
Java
public class Solution {
public boolean canJump(int[] nums) {
int curr = 0;
int right = 1;
while (curr <= right) {
int val = nums[curr];
if (curr + val > right) {
right = curr + val;
}
if (right >= nums.length - 1) {
return true;
}
curr++;
}
return false;
}
}
Python
class Solution:
def canJump(self, nums: List[int]) -> bool:
curr: int = 0
right: int = 0
while curr <= right:
val = nums[curr]
right = max(right, curr + val)
if right >= len(nums) - 1:
return True
curr += 1
return False
Complexity
- ⏰ Time complexity:
O(n), as we iterate through the array at most once. - 🧺 Space complexity:
O(1), as we use a constant amount of extra space.
Method 6 - Using Graphs
complete later