Subramanya's Digital Garden

Recent Notes

55. Jump Game

6 min read

Intuition

When you first see this problem, your mind might jump (pun intended) to graph traversal algorithms like Breadth-First Search (BFS) or Depth-First Search (DFS). You could think of each array index as a node and each possible jump as an edge. You could then explore all possible paths from the start to see if any of them land on the final index.

This would work, but it might be overkill. Exploring every path can be computationally expensive, especially if the jump lengths are large. This often leads to a “Time Limit Exceeded” error on platforms like LeetCode.

So, let’s reframe the question. Instead of asking “What path should I take?”, let’s ask a simpler, more powerful question: “What’s the farthest I can possibly reach at any given moment?”

This shift in perspective is the key. We don’t need to map out the entire journey. We just need to be optimistic and keep track of our maximum possible reach. As long as we never get to a point where the next step is beyond our reach, we’re still in the game. This is the essence of a greedy approach.

Approach

Our greedy strategy will be to iterate through the array, maintaining a variable that tracks the maximum index we can reach. Let’s call it max_reach.

  1. Initialize max_reach = 0. At the beginning, the farthest we can reach is our starting position, index 0.
  2. Iterate through the array from left to right, with an index i.
  3. At each index i, we first perform a critical check: Can we even get here? We can only be at index i if it’s within our current max_reach. If i > max_reach, it means we’ve encountered a gap of zeros (or small numbers) that we couldn’t jump over. We are stuck, and it’s impossible to proceed. In this case, we can immediately return false.
  4. If we can reach index i, we then calculate the potential new farthest reach from this spot. From index i, we can jump up to nums[i] steps, reaching as far as i + nums[i].
  5. We update our global max_reach to be the maximum of its current value and this new potential reach. This is our greedy choice: we’re always updating our horizon to the farthest possible point. The line would look like: max_reach = max(max_reach, i + nums[i]).
  6. If our max_reach ever touches or surpasses the last index of the array, we know it’s possible to win. We can stop and return true.

If we complete the loop without ever getting stuck (i.e., the i > max_reach check never fails), it implies we were able to successfully reach the last element.

Let’s trace this with nums = [3, 2, 1, 0, 4]:

  • Start: max_reach = 0, last_index = 4.
  • i = 0: i is not greater than max_reach (0 is not > 0). From here, we can reach 0 + nums[0] = 3. Update max_reach = max(0, 3) = 3.
  • i = 1: i is not greater than max_reach (1 is not > 3). From here, we can reach 1 + nums[1] = 3. Update max_reach = max(3, 3) = 3.
  • i = 2: i is not greater than max_reach (2 is not > 3). From here, we can reach 2 + nums[2] = 3. Update max_reach = max(3, 3) = 3.
  • i = 3: i is not greater than max_reach (3 is not > 3). From here, we can reach 3 + nums[3] = 3. Update max_reach = max(3, 3) = 3.
  • i = 4: i is greater than max_reach (4 > 3). We’ve reached a point that is beyond our horizon. We can’t get here. Return false.

This simple, linear scan gives us the correct answer efficiently.

Complexity

  • Time complexity:

    O(n)

    We do a single pass through the array from the beginning to the end. Therefore, the time complexity is linear with respect to the number of elements in the input array.

  • Space complexity:

    O(1)

    We only use a few variables to keep track of our state (max_reach, the loop index i, etc.), regardless of the size of the input array. This means our space usage is constant.

Code

Python

from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        """
        Determines if the last index can be reached using a greedy approach.
        """
        max_reach = 0
        n = len(nums)

        # Iterate through the array indices.
        # We only need to iterate as long as our current position `i`
        # is within our `max_reach`.
        for i in range(n):
            # If the current index `i` is greater than the farthest we could have reached,
            # it means we are stuck and can't proceed.
            if i > max_reach:
                return False
            
            # Update the maximum reach based on the jump power from the current index.
            # This is the greedy choice: always extend the horizon as much as possible.
            max_reach = max(max_reach, i + nums[i])
            
            # An optional optimization: if our reach already covers the goal, we're done.
            if max_reach >= n - 1:
                return True
                
        # If the loop completes, it means the last index was reachable.
        # This line is only reached if the optimization is not hit, for example,
        # in an array like [0] or [1].
        return True

How to recognize similar problems

This greedy pattern is quite common. You can suspect a similar approach is needed when a problem has these characteristics:

  1. Array Traversal with Rules: The problem involves moving through an array where the value at an index dictates the rules of movement (e.g., how far you can jump, where you can go next).
  2. Possibility vs. Optimality: The question asks “Is it possible?” rather than “What is the best way?“. For example, “Jump Game II” asks for the minimum number of jumps, which requires a slightly more complex approach (often BFS). “Can you reach the end?” is a classic sign for this greedy reachability pattern.
  3. Forward-Looking Decisions: The choice at your current position affects the range of future choices. The greedy strategy simplifies this by consolidating all future choices into a single, optimistic metric: the farthest possible reach.

How to remember the concept

A great way to remember this concept is the “Horizon Analogy”:

Imagine you are a traveler. The max_reach variable is your horizon—the farthest point you know you can get to. You start walking forward (for i in ...). With every step you take, you check if you are still within your known horizon (if i > max_reach). If you step past it, you’re lost in an unreachable land. From every spot you stand on, you look ahead with your binoculars (i + nums[i]) and update your horizon to the new farthest point you can see. Your goal is simply to ensure your horizon eventually extends to or beyond your destination.

This analogy captures the core idea: keep moving forward as long as you’re on safe ground, and always be optimistic about how far you can go next.

Graph View