Reaching the last swap station

A courier runs an electric trike along a straight road of battery-swap stations. Each station racks a different battery, and a weak one strands the rider short of the depot.

The problem

Stations are numbered 0 to n - 1, and the depot is the last one. The trike starts at station 0 on the battery racked there. The battery at station i carries it past at most reach[i] stations, so from i the rider may pull in anywhere from i + 1 to i + reach[i] and swap for whatever is racked there. Stopping early is allowed; riding past i + reach[i] is not. A reach of 0 is a flat battery.

Decide whether the trike can get from station 0 to the depot.

Input. reach — a list of non-negative integers, how far forward each racked battery carries the trike.

Output. True if the depot is reachable, False otherwise.

Example.

reach = [1, 4, 2, 0, 1, 3]  ->  True

Station 0's battery only reaches station 1, but the one racked there carries the trike four stations on, past the flat battery at station 3 and onto the depot.

A second example, where a strong battery sits out of reach:

reach = [4, 1, 2, 0, 0, 2, 1]  ->  False

From station 0 the rider reaches stations 1, 2, 3 or 4, and none of those opens anything past station 4 — stations 3 and 4 are flat. Station 5 has plenty of charge and is never used, because the trike cannot park there.

Constraints.

• 1 <= len(reach) <= 10^5
• 0 <= reach[i] <= 10^5
• A one-station road is already at the depot

Hints

Approach

Brute force

Search every route: from each station, branch on every station it can reach. Twenty stations already run to millions of paths, and the worst case is exponential. Memoising per station brings it to O(n²) — still 10¹⁰ steps at the limit.

The insight

Where you stopped on the way does not matter; only the furthest station any route has opened up matters, and that is one number.

Reachability only moves forward and stopping short is free, so the reachable set is always a prefix 0..furthest — one number in place of the branching search. Scanning left to right, station i is usable exactly when i <= furthest, and using it replaces furthest with max(furthest, i + reach[i]). The first station failing that test is a wall: nothing past it is reachable either, since everything before it is already counted.

Algorithm

1. Set furthest = 0 and last = len(reach) - 1.
2. For each station i: if i > furthest, return False — the road is walled.
3. Otherwise set furthest = max(furthest, i + reach[i]).
4. If furthest >= last, return True.
5. Return True when the loop ends.

Complexity

Time O(n) — one comparison and one addition per station. Space O(1) — two integers, however long the road.

Solution

"""Reaching the last swap station — greedy furthest reach in one pass."""


def solve(reach):
    if not reach:
        return False
    last = len(reach) - 1
    furthest = 0
    for i, charge in enumerate(reach):
        # invariant: every station in 0..furthest is reachable, so a station
        # past `furthest` is a wall and nothing beyond it can be opened.
        if i > furthest:
            return False
        if i + charge > furthest:
            furthest = i + charge
        if furthest >= last:
            return True
    return True

TESTS = [
    (([1, 4, 2, 0, 1, 3],), True),
    (([4, 1, 2, 0, 0, 2, 1],), False),
    (([2, 3, 0, 0, 1],), True),
    (([3],), True),
    (([0, 5],), False),
    (([1, 1],), True),
    (([1, 1, 1, 1],), True),
]

Pitfalls

• Reading reach[i] as an exact hop rather than a maximum. On [2, 3, 0, 0, 1] that forces 0 → 2, where the battery is flat, and reports False. Pulling in early at station 1 reaches the depot: the answer is True.
• Updating furthest before checking the wall. Station 5 in [4, 1, 2, 0, 0, 2, 1] then donates its charge although the trike can never park there, and the answer flips to True.
• Testing furthest >= len(reach) for the early exit. The depot is index n - 1, so a ride landing exactly on it is rejected: [1, 1] returns False.

Variants

• The scrap copper spread — one carried number again, but it summarises the past rather than the reachable future, and the answer is a quantity, not a yes or no.
• Empty pockets to the tail — another left-to-right walk with one extra index, but it writes as it goes.