Jump Game 1 - Check if it reaches last index

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.

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.

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

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.

---
title: Recursion tree for nums=[3,2,1,0,4]
---
graph TD;
	A(0) ---|1| B(1)
	A ---|2| C(2)
	A ---|3| D(3):::deadend
	B ---|1| E(2)
	B ---|2| F(3):::deadend
	E ---|1| G(3):::deadend
	C ---|1| H(3):::deadend
 
classDef deadend fill:#ffcccc,color:#900,font-weight:bold;

Code

Java

class Solution {

    public boolean canJump(int[] nums) {
        // Start recursion from the first index
        return dfs(0, nums);
    }

    // Recursive helper method to explore jumps
    private boolean dfs(int pos, int[] nums) {
        // Base case: If we reach or pass the last index, return true
        if (pos >= nums.length - 1) {
            return true;
        }

        // Explore all jumps from the current position
        for (int nextPos = 1; nextPos <= nums[pos]; nextPos++) {
            if (dfs(pos + nextPos, nums)) {
                return true;
            }
        }

        // If no valid path is found, return false
        return false;
    }
}

Python

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        def dfs(position: int) -> bool:
            # Base case: If we reach the last index, return True
            if position >= len(nums) - 1:
                return True
            
            # Explore all jumps from the current position
            for next_pos in range(1, nums[position] + 1):
                if dfs(position + next_pos):
                    return True
            
            # If no valid path is found, return False
            return False
        
        # Start recursion from the first index
        return dfs(0)

Complexity

⏰ Time complexity: O(n^n). In the worst case, each index allows up to n jumps, leading to n recursive calls per index.
- This results in a O(n^n) complexity due to the height of the recursion tree expanding exponentially with n.
🧺 Space complexity: O(n). The recursion stack can grow up to n levels in the worst case.

Method 2 - Top Down 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.

Code

Java

class Solution {
    public boolean canJump(int[] nums) {
        // Create a cache for memoization
        Map<Integer, Boolean> cache = new HashMap<>();
        
        // Call the helper method starting from the first index
        return dfs(0, nums, cache);
    }

    // Helper method for recursive exploration with caching
    private boolean dfs(int pos, int[] nums, Map<Integer, Boolean> cache) {
        // Base case: If we reach or exceed the last index, return true
        if (pos >= nums.length - 1) {
            return true;
        }

        // Check if the current position is already in the cache
        if (cache.containsKey(pos)) {
            return cache.get(pos);
        }

        // Explore all possible jumps from the current position
        int maxJump = nums[pos];
        for (int nextPos = 1; nextPos <= maxJump; nextPos++) {
            if (dfs(pos + nextPos, nums, cache)) {
                cache.put(pos, true); // Cache the result
                return true;
            }
        }

        // If no valid path can be found, cache the result and return false
        cache.put(pos, false);
        return false;
    }
}

Python

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cache = {}

        def dfs(position: int) -> bool:
            # Base case: If we reach or exceed the last index
            if position >= len(nums) - 1:
                return True
            
            # Check cache
            if position in cache:
                return cache[position]

            # Explore jumps from this position
            max_jump = nums[position]
            for next_pos in range(1, max_jump + 1):
                if dfs(position + next_pos):
                    cache[position] = True  # Cache result
                    return True
            
            # Cache negative result if no path works
            cache[position] = False
            return False

        # Start recursion from index 0
        return dfs(0)

Complexity

⏰ Time complexity: O(n^2). Each index is processed at most once due to caching.
- For each index, we can explore up to nums[i] possible jumps, leading to a worst-case O(n^2) for n indices.
🧺 Space complexity: O(n). The cache requires O(n) space for storing results of each index.

Method 3 - 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

class Solution {

    public boolean canJump(int[] nums) {
        int goal = nums.length - 1; // Start with the goal at the last index

        // Iterate from right to left
        for (int i = nums.length - 2; i >= 0; i--) {
            // Check if the current index can reach the current goal
            if (i + nums[i] >= goal) {
                goal = i; // Shift the goal backward to this index
            }
        }

        // At the end, check if the goal has shifted all the way back to index 0
        return goal == 0;
    }
}

Python

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1  # Start with the goal at the last index
        
        # Iterate from right to left
        for i in range(len(nums) - 2, -1, -1):
            # Check if the current index can reach the current goal
            if i + nums[i] >= goal:
                goal = i  # Shift the goal backward to this index
        
        # At the end, check if the goal has shifted all the way back to index 0
        return goal == 0

Complexity

⏰ Time complexity: O(n), where n is 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 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), where n is 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

Jump Game 1 - Check if it reaches last index

Problem

Examples

Similar Problems

Solution

Video explanation

Method 1 - Brute Force Using Recursion

Code

Java

Python

Complexity

Method 2 - Top Down DP

Code

Java

Python

Complexity

Method 3 - Greedy - Starting from end

Approach

Code

Java

Python

Complexity

Method 4 - Greedy - Starting from Start

Code

Java

Python

Rust

Complexity

Method 5 - Greedy - kind of 2 pointers

Code

Java

Python

Complexity

Method 6 - Using Graphs

Comments