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.

Additional information

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

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.

Top-Down Dynamic Programming (Memoization)

Intuition

A highly literal way to solve this is to simulate every single possible jump from the first index. We can use a recursive Depth-First Search (DFS).

Starting at index 0, we look at the value nums[0]. If it is 3, we branch out and recursively check if jumping 1, 2, or 3 steps eventually leads to the last index. If any of those branches successfully reach the end, we return True.

Because many branches might land on the exact same index and redundantly calculate the exact same future paths, we use a memo dictionary (cache) to store whether a specific index is a "good" index (can reach the end) or a "bad" index.

Algorithm

1. If nums has only 1 element, return True (you are already at the last index).
2. Initialize a memo dictionary to cache results.
3. Define a recursive helper function dfs(i):

• If i >= len(nums) - 1, we reached the destination! Return True.
• If i is already in memo, return its cached boolean value.
• Get the maximum jump length from the current index: furthest_jump = min(i + nums[i], len(nums) - 1).
• Loop next_step from i + 1 up to furthest_jump.
• If dfs(next_step) returns True, cache memo[i] = True and return True.
• If all jumps fail, cache memo[i] = False and return False.

4. Call dfs(0) and return the result.

def can_jump(nums: list[int]) -> bool:
    memo = {}
    n = len(nums)
    
    def dfs(i):
        if i >= n - 1:
            return True
            
        if i in memo:
            return memo[i]
            
        furthest_jump = min(i + nums[i], n - 1)
        
        for next_step in range(i + 1, furthest_jump + 1):
            if dfs(next_step):
                memo[i] = True
                return True
                
        memo[i] = False
        return False
        
    return dfs(0)

Time & Space Complexity

• Time complexity: O(N^2)

• Reason: For every single index in the array (N), we might potentially iterate through all subsequent indices (up to N) to check jumps. Caching prevents redundant full-depth trees, but the nested loop structure remains quadratic in the worst case.

• Space complexity: O(N)

• Reason: The recursion stack and the memo dictionary will both hold up to N elements.

Greedy Algorithm - Optimal

Intuition

The DP approach works backwards from every possibility, but we can solve this in a single forward pass using a Greedy Algorithm.

Instead of checking every path, we simply keep track of the max_reachable index. As we iterate through the array, we update this max_reachable index to be the maximum of its current value or current_index + jump_length.

The only way we fail is if our current_index is strictly greater than our max_reachable index! This means we have encountered a 0 (or a series of small jumps) that trapped us, and we mathematically cannot travel far enough to even reach the current element we are looking at.

Algorithm

1. Initialize a variable max_reachable = 0. This stores the absolute furthest index we have the power to jump to.
2. Iterate i from 0 to len(nums) - 1.
3. The Trap Check: If i > max_reachable, it means we are currently trying to process an index that we can't even reach. We are stuck! Return False.
4. The Greedy Update: Update max_reachable to be the maximum of what it currently is, or i + nums[i] (the furthest we can jump from the current index).
5. Early Exit (Optional): If max_reachable >= len(nums) - 1, we already know we have enough power to reach the end. Return True.
6. If the loop finishes completely, it means we reached the end successfully. Return True.

def can_jump(nums: list[int]) -> bool:
    max_reachable = 0
    n = len(nums)
    
    for i in range(n):
        # If we reached an index that is beyond our maximum reach, we are stuck
        if i > max_reachable:
            return False
            
        # Greedily update the furthest index we can possibly reach
        if i + nums[i] > max_reachable:
            max_reachable = i + nums[i]
            
        # Early exit if we can already reach or surpass the last index
        if max_reachable >= n - 1:
            return True
            
    return True

Time & Space Complexity

• Time complexity: O(N)

• Reason: We iterate through the nums array exactly one time. Operations inside the loop are constant time O(1).

• Space complexity: O(1)

• Reason: We only use a single integer variable max_reachable to track our state, completely avoiding recursion stacks and cache dictionaries.