Jump Game — The Creek Crossing

Boss 2: The Creek Crossing

Boss 1 taught the greedy reflex on money. This boss teaches it on movement, and introduces the single most reusable idea in this dungeon: reach. Half the greedy problems you'll ever meet are secretly "track the farthest point you can get to."

The story

The hiking trail dead-ends at a creek. Someone helpful has laid stepping stones and painted a number on each: the maximum distance you can jump from that stone. Jump shorter if you like, never longer.

Today's stones:

stone:    0    1    2    3    4
power:    2    3    1    1    4

You stand on stone 0. The far bank is stone 4. Stone 0 lets you hop to stone 1 or 2. From stone 1, its power of 3 reaches stones 2, 3, or 4. So: 0 → 1 → 4. Crossable.

Now the cursed layout:

stone:    0    1    2    3    4
power:    3    2    1    0    4

Every path funnels you onto stone 3, a dud with power 0. You stand there, the far bank four feet away, going nowhere. Not crossable.

The problem, dressed up properly

You are given an integer array nums. You start at the first index, and each element is your maximum jump length from that position. Return true if you can reach the last index, false otherwise.

LeetCode 55. Officially "Jump Game", spiritually "can you cross the creek."

The naive attempt

Treat it as a graph: each stone connects to every stone within its power, then DFS from stone 0. Dungeon 11 muscle memory.

def can_cross(nums):
    n = len(nums)
    seen = set()
 
    def dfs(i):
        if i >= n - 1:
            return True
        if i in seen:
            return False
        seen.add(i)
        for step in range(nums[i], 0, -1):
            if dfs(i + step):
                return True
        return False
 
    return dfs(0)

Works, and with memoization it lands around O(n²) in the worst case: each of n stones may fan out to n neighbors. Also it's a lot of machinery for a yes/no question about walking forward. The creek does not require a graph theory degree.

The weapon: carry your reach

Walk the stones left to right with one variable: farthest, the highest-numbered stone reachable using everything seen so far.

At stone i, two things happen:

1. Am I even allowed to be here? If i > farthest, no combination of earlier jumps lands on or beyond this stone. There's a gap behind you. Return false.
2. Update the reach. Standing on i with power nums[i] means stone i + nums[i] is now reachable. Take the max.

Why is this greedy sound? Because jump lengths are anything up to the power. If farthest covers stone i, you genuinely can stand there, some earlier stone launches far enough and you jump shorter on purpose. Reach never lies, so one number summarizes every possible path.

def can_cross(nums: list[int]) -> bool:
    farthest = 0
    for i, power in enumerate(nums):
        if i > farthest:          # stranded: a gap nobody can jump
            return False
        farthest = max(farthest, i + power)
        if farthest >= len(nums) - 1:
            return True           # far bank already in range
    return True

One pass, one integer, no graph.

Watching it work

Crossable creek [2, 3, 1, 1, 4]:

stone  power   check           farthest
0      2       0 ≥ 0 ok        max(0, 0+2) = 2
1      3       1 ≥ 1 ok        max(2, 1+3) = 4 → reaches last stone, True ✓

Two steps and done. The cursed creek [3, 2, 1, 0, 4]:

stone  power   check           farthest
0      3       ok              3
1      2       ok              3
2      1       ok              3
3      0       ok              3   (the dud: adds nothing)
4      4       4 > 3 → False ✗

farthest freezes at 3 because stones 1, 2, 3 all reach at most stone 3. When the walk arrives at stone 4, the gap check fires. Stranded.

Gotchas

1. Checking the gap after updating reach. Order matters. Ask "can I stand here?" before letting stone i contribute its power. A stone you can't reach donates nothing, and max(farthest, i + power) from an unreachable stone is fiction.

2. Thinking jumps are exact. Power 3 means up to 3. If jumps were exact, greedy reach breaks completely and the problem becomes a real graph search. Read the rules before picking the weapon.

3. Overcomplicating the single-stone creek. nums = [0]: you start on the last stone. Already there, answer true. The loop handles it because farthest = 0 covers index 0, but only if your early-return condition uses >= against len(nums) - 1.

4. Simulating actual jumps. You never jump in this algorithm. You walk every stone and merge its range into the frontier. Students who try to simulate "the best jump" from each stone end up in Boss 3's problem by accident, and get it wrong, because picking the single best jump is subtler than it looks.

Complexity

One walk down the stones.

Time: O(n). Space: O(1).

Boss down. XP gained.

You step onto the far bank and glance back at the creek. From here, the painted numbers look less like a puzzle and more like a wavefront you surfed.

What you walked away with:

• Reach: one integer summarizing every possible sequence of moves on a line
• The stranded check i > farthest catches impossibility the moment it becomes true
• "Up to k" movement is what makes greedy reach valid, exact-k would break it
• BFS intuition from Dungeon 11 compresses to O(1) space when the graph is a line

Next up: Boss 3 — The Creek Crossing Sprint. Same creek, same painted stones, but now there's a race on: cross in the fewest jumps. Reach comes back with a second frontier line, and the answer falls out of watching where each "jump wave" ends.