You are given an integer array nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from position i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return true if you can reach nums[n - 1], or false otherwise.

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 <= 10^4
• 0 <= nums[i] <= 10^5

Jump Game

Problem Description

You are given an integer array nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from position i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return true if you can reach nums[n - 1], or false otherwise.

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 <= 10^4
• 0 <= nums[i] <= 10^5

Naive Solution

A naive solution would involve recursively exploring all possible jump combinations. Starting from the first element, we can try all possible jump lengths up to the value at that index. If any of these combinations lead to the end, we return true. Otherwise, if we exhaust all combinations without reaching the end, we return false.

def can_jump_naive(nums):
    def solve(index):
        if index >= len(nums) - 1:
            return True
        
        max_jump = nums[index]
        for jump in range(1, max_jump + 1):
            if solve(index + jump):
                return True
        return False
    
    return solve(0)

Optimal Solution

A more efficient solution involves iterating through the array and keeping track of the furthest reachable index. At each index i, we check if i is within the reachable range. If it is, we update the furthest reachable index by taking the maximum of the current reachable index and i + nums[i]. If at any point i is beyond the reachable range, it means we cannot reach the current index and therefore cannot reach the end. If the furthest reachable index is greater than or equal to the last index in the array, then we can reach the end.

def can_jump(nums):
    reachable = 0
    for i, num in enumerate(nums):
        if i > reachable:
            return False
        reachable = max(reachable, i + num)
    return reachable >= len(nums) - 1

Big(O) Run-time Analysis

The optimal solution iterates through the array once. Therefore, the run-time complexity is O(n), where n is the length of the input array nums.

The naive solution's run-time complexity is O(2^n) because, in the worst-case scenario, each element can have multiple jump options, leading to an exponential number of branches in the recursion tree.

Big(O) Space Usage Analysis

The optimal solution uses only a single variable reachable to keep track of the furthest reachable index. Thus, the space complexity is O(1), which means constant space.

The naive solution uses recursion. Therefore, the space complexity is O(n) in the worst case due to the recursion depth.

Edge Cases

1. Empty array: If the input array is empty, the problem statement doesn't specify what to do. However, we can assume it should return false as there is no last element to reach.
2. Single-element array: If the input array contains only one element, we are already at the end, so we should return true.
3. Array with all zeros: If the array contains only zeros (except possibly the first element), we can only reach the end if the array has length 1. Otherwise, we will be stuck at the first element (or some later zero), so the result is false.
4. Large jump from the beginning: If the first element allows us to jump beyond the end of the array, we can reach the end immediately. In this case, the algorithm should return true quickly.
5. Zero in the middle: If we encounter a zero in the middle of the array, and we cannot jump over it, we are stuck. This is the key situation that the algorithm must handle correctly.

Here's the can_jump function incorporating handling some of the edge cases:

def can_jump_edge_cases(nums):
    if not nums:
        return False # Handle empty array case
    
    if len(nums) == 1:
        return True # Handle single-element array case
        
    reachable = 0
    for i, num in enumerate(nums):
        if i > reachable:
            return False
        reachable = max(reachable, i + num)
        if reachable >= len(nums) -1:
            return True # Optimization: Early return if we can reach the end
    return reachable >= len(nums) - 1