Water for the whole ring

A heritage railway runs one locomotive round a closed loop of halts. Only one halt on the loop can begin the day, and testing them one at a time is the slow way to find it.

The problem

The line is a circle of n halts, numbered 0 to n - 1 clockwise, and the locomotive always runs clockwise. Every halt has a water column: pulling in at halt i puts column[i] gallons in the tank. Running from halt i to the next halt round the circle burns leg[i] gallons, and the leg out of halt n - 1 returns to halt 0.

The locomotive starts at whichever halt the shed picks, tank empty, takes on that halt's water and runs the full circle back. The tank never overflows. A run fails when a leg needs more gallons than the tank holds as it sets off; arriving with an empty tank is fine, because the next column refills it.

Report the halt the day can start from, or -1 if none works. Where a start exists, it is the only one.

Input. column — a list of integers, gallons delivered at each halt. leg — a list of the same length, gallons burned on the leg out of each halt.

Output. The index of the starting halt, or -1.

Example.

column = [4, 6, 3, 5, 2], leg = [5, 2, 6, 3, 4]   ->  1

From halt 1 the tank reads 4, 1, 3, 1 and 0 as it reaches halts 2, 3, 4, 0 and 1 again. Halt 0 fails immediately: 4 gallons in, a 5-gallon leg out.

A second example, where the fullest column is the wrong answer:

column = [5, 1, 4, 2], leg = [1, 6, 1, 4]   ->  2

Halt 0 spares 4 gallons, more than any other, and still strands the locomotive on the leg out of halt 1: 6 burned against 5 in the tank.

Constraints.

• 1 <= n <= 10^5
• len(column) == len(leg) == n
• 0 <= column[i] <= 10^4
• 0 <= leg[i] <= 10^4

Hints

Approach

Brute force

Simulate the whole circle from each halt, abandoning an attempt the first time the tank goes negative. That is n starts times n legs — 10¹⁰ steps at the upper constraint.

The insight

If a circuit starting at halt s runs dry on the leg out of halt j, every halt from s to j fails too, so the next candidate is j + 1.

For any halt k between s and j, the tank was non-negative arriving at k, so the surplus over k..j is at most the surplus over s..j, which is negative. Each halt is ruled out once and never re-examined, so one sweep covers every start. The precondition is the total: sum(column) >= sum(leg) guarantees a survivor, because the last candidate the sweep opens carries the whole surplus.

Algorithm

1. If sum(column) < sum(leg), report -1.
2. Set start = 0 and tank = 0.
3. For each halt i in order, add column[i] - leg[i] to tank.
4. If tank is negative, set start = i + 1 and tank = 0.
5. Report start when the sweep ends.

Complexity

Time O(n) — two passes, or one if the totals accumulate alongside. Space O(1) — two integers, whatever the length of the line.

Solution

"""Water for the whole ring — one sweep that restarts the candidate halt at each failure."""


def solve(column, leg):
    # No start can exist unless the ring delivers at least what it burns.
    if sum(column) < sum(leg):
        return -1

    start, tank = 0, 0
    for i in range(len(column)):
        tank += column[i] - leg[i]
        if tank < 0:
            # Every halt from `start` to `i` runs dry by `i`, so skip them all.
            # invariant: from `start` to the halt reached so far the tank stayed >= 0
            start, tank = i + 1, 0
    return start

TESTS = [
    (([4, 6, 3, 5, 2], [5, 2, 6, 3, 4]), 1),
    (([2, 3, 1], [3, 4, 2]), -1),
    (([5, 1, 4, 2], [1, 6, 1, 4]), 2),
    (([4, 1], [1, 4]), 0),          # tank reaches exactly 0 — not a failure
    (([2, 0, 5], [1, 4, 2]), 2),    # the only start is the last halt
    (([7], [7]), 0),                # single halt, column exactly covers the loop
    (([3], [5]), -1),               # single halt, short by two gallons
]

Pitfalls

• Treating an empty tank as a failure. With if tank <= 0, the line column = [4, 1], leg = [1, 4] restarts on the last leg and reports -1, when halt 0 gets round with exactly nothing to spare. Only a negative tank is a failure.
• Skipping the totals check. The sweep always ends holding some index, so without step 1 the impossible line column = [2, 3, 1], leg = [3, 4, 2] comes back as halt 3 — one off the end of a three-halt line — instead of -1.
• Restarting at i instead of i + 1. Halt i is the one whose leg drained the tank, so it cannot begin a circuit; on the first example that returns 0.
• Forgetting to zero the tank on a restart. That debt belongs to halts already discarded, and carrying it forward pushes the answer past the start.

Variants

• The exchange argument — why a one-pass choice may discard candidates without checking them.