Domain 2MediumCORE

Jump Game

We are given an array nums where each element represents the maximum jump length from that specific index. We start at index 0 and need to determine if we can reach the last index of the array.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Greedy

55. Jump Game

Model: qwen3.5:9b
Topics: Array,Greedy
FAANG asked: 1
Acceptance rate: 35.2%


Problem Breakdown

We are given an array nums where each element represents the maximum jump length from that specific index. We start at index 0 and need to determine if we can reach the last index of the array.

Inputs: A list of non-negative integers (nums). Outputs: Boolean value indicating reachability. Constraints & Edge Cases:

  • Array size is between 1 and 3×1043 \times 10^4. This rules out empty arrays but requires an efficient solution (better than quadratic).
  • Values are non-negative (≥0\ge 0), so we don’t need to handle negative jump lengths.
  • If the array has only one element, we start at index 0 which is also the last index; this should return True.

Intuition

A naive approach would be Depth-First Search (DFS) or Breadth-First Search (BFS), trying every possible path from the current position to see if any lead to the end. However, since we can jump multiple steps at once, branching factor is high (O(2N)O(2^N) in worst case). This will time out on large inputs.

The key insight for a greedy solution: We don’t need to track specific paths or combinations of jumps. Instead, we only care about the furthest index reachable so far (max_reach).

As we iterate through the array from left to right:

  1. If our current position i is beyond what we can reach (i > max_reach), it means there’s a gap in jumps that blocks us, and we cannot proceed further. We return False.
  2. Otherwise, we update max_reach by considering the jump from index i: max(max_reach, i + nums[i]).

If we complete the loop without getting blocked, it implies every step was reachable, so we can reach the end (or have already passed it).

Approach

  1. Initialize a variable farthest to track the maximum index reachable from any point visited so far. Start at 0.
  2. Iterate through each index i in the array up to the second-to-last element. We stop before the last one because if we can reach it, success is guaranteed; no need to jump from the last index.
  3. Inside the loop:
    • Check if current index i > farthest. If true, return False immediately (we are stuck).
    • Update farthest = max(farthest, i + nums[i]).
  4. After iterating through all reachable indices without getting blocked, return True.

Complexity Analysis

  • Time: O(N)O(N) where N is the length of nums. We perform a single pass over the array with constant-time operations inside the loop.
  • Space: O(1)O(1). We only use two variables (farthest and index counter), regardless of input size.

Solution

def canJump(nums):
    """
    Determines if it's possible to reach the last index from index 0.
    
    Args:
        nums (List[int]): Array where each element is max jump length at that position.
        
    Returns:
        bool: True if last index is reachable, False otherwise.
    """
    farthest = 0
    
    # Iterate up to the second-to-last index because we don't need 
    # to calculate a jump from the final destination itself.
    for i in range(len(nums) - 1):
        # If current position exceeds our furthest reachable point,
        # it's impossible to proceed further.
        if farthest < i:
            return False
        
        # Update the maximum index we can reach with a jump from here
        farthest = max(farthest, i + nums[i])

    return True

Edge Cases Handled

  • Single Element Array: The loop range(len(nums) - 1) becomes empty (e.g., length 1). Function skips the loop and returns True, which is correct since we are already at the end.
  • Blocked Path Early On: If a zero appears early that prevents reaching subsequent indices, farthest will not increase enough to cover future indices, causing i > farthest check to trigger correctly on the next iteration or immediately if stuck right away.
  • Large Jump Values: The logic handles large jump lengths naturally by updating farthest. Since Python integers handle arbitrary size (and constraints are within standard integer limits), overflow is not a concern here compared to languages like C++/Java, though we still check reachability bounds rather than just summing values.