p82 — Gas Station

Source: LeetCode 134 · Medium · Topics: Greedy, Prefix Sums Companies (2024–2025): Amazon (high), Google (medium), Meta (medium), Uber (medium) Loop position: The failure-point skip lemma. Tests whether you can prove a one-pass greedy correct, not just simulate.

1. Quick Context

n gas stations in a circle. gas[i] available at station i; cost[i] to travel from i to i+1. Start with empty tank. Return the starting index that lets you complete the circle, or -1 if impossible.

Key facts:

  • If sum(gas) < sum(cost): impossible. Return -1.
  • Otherwise a unique-modulo-symmetry start exists.

One-pass greedy: Track total (overall surplus) and tank (current segment surplus). If tank drops below 0 at station i, no start in [start, i] works; reset start = i+1, tank = 0.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/gas-station/

STOP. 25-min timer. The lemma “if you fail at i starting from s, no j in [s, i] succeeds” is the whole problem.

3. Prerequisite Concepts

  • Prefix sums on a circular array.
  • Pigeonhole / invariant-style proofs.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Find a starting index so the running tank stays ≥ 0 around the circle.

2. Clarify: Negative tank disallowed between stations; -1 if no valid start.

3. Examples: gas=[1,2,3,4,5], cost=[3,4,5,1,2] → start=3.

5. Brute: Try each start; simulate full circle. O(n²).

6. Target: O(n) one pass.

7. Pattern: Failure-point skip + global feasibility check.

8. Develop: see solution.py.

9. Test: sum(gas) < sum(cost); single station; all costs zero.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 The skip lemma

Claim: If starting from s, the tank first goes negative at station i (i.e., after refueling at i and trying to depart for i+1), then no start j ∈ [s, i] is valid.

Proof: Let T(a, b) = net tank from a (start tank 0) reaching b (after fueling at b but before departing). By assumption T(s, j) ≥ 0 for all j ∈ [s, i-1] and T(s, i) < 0. For any j ∈ (s, i]: T(j, i) = T(s, i) - T(s, j-1) ≤ T(s, i) < 0 (since T(s, j-1) ≥ 0). So j also fails by station i. ∎

Therefore: when failure happens at i, skip past i: reset start to i+1.

6.2 Why one pass suffices

Combined with the lemma, each station is visited at most once as part of an attempt. If total = sum(gas - cost) ≥ 0, the surviving candidate start must be valid (proof: suppose not; then it fails somewhere, contradiction since total surplus is non-negative and skips already eliminated all earlier candidates).

6.3 Why total ≥ 0 guarantees existence

sum(gas - cost) ≥ 0 ⟹ exists a circular arrangement with non-negative running prefix from some start (a standard “rotate to minimum” argument).

6.4 Equivalent: “rotate-to-minimum-prefix” formulation

Compute diff[i] = gas[i] - cost[i]. Best start = index immediately after the global minimum prefix sum. Equivalent answer; less elegant code than the skip greedy but easier to prove.

6.5 Family: circular prefix-sum problems

  • LC 134 Gas Station (this).
  • LC 918 Max Subarray Sum Circular (Kadane + suffix or total-min variant).
  • LC 525 Contiguous Array (prefix sum + hashmap).
  • LC 974 Subarray Sums Divisible by K.

The common move: convert circular to linear via doubled array or via algebraic identity.

6.6 What changes if tank capacity is bounded?

If tank cap C exists, the skip lemma still holds for “≤ 0” failures but you can no longer carry excess from rich-gas regions. Becomes a windowed problem; often solvable with monotonic deque on prefix sums.

7. Anti-Pattern Analysis

  1. Reset start to i (not i+1) — i itself already failed; off-by-one.
  2. Don’t compute global total — when no valid start exists, your greedy still produces a “candidate” that doesn’t work.
  3. Two-loop O(n²) — works but signals you missed the lemma.
  4. Reset tank but not start — wrong; the candidate must move past the failure point.
  5. Track minimum prefix without proving it’s optimal — works but unconvincing for a senior interview.
  6. Allow negative tank temporarily, hoping later gas refills — rule violation; must remain ≥ 0 at every step.

8. Skills & Takeaways

  • Failure-point skip greedy.
  • Global feasibility check via total surplus.
  • Circular ↔ linear conversion.

9. When to Move On

  • Solve cold in 20 min, prove the skip lemma unprompted.
  • Articulate why total >= 0 is necessary AND sufficient.
  • Cite Max Subarray Circular as a sibling.

10. Company Context

  • Amazon: L5/L6; very common screen.
  • Google: L5; greedy correctness probe.
  • Meta: E5; expects the lemma proof.
  • Uber: mid; logistics-flavor problem.

Strong: “One-pass skip greedy with global feasibility check; proves the skip lemma; cold; cites circular-prefix family.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
Skip lemmaNoneAfter hintProves cold+ cites prefix-min equivalence
Total checkMissesAfter testCold+ necessity & sufficiency proof
Off-by-oneResets to iAfter testi+1 cold+ invariant comment
FamilyNoneNoneCircular Kadane+ bounded-tank deque variant

12. Level Delta

  • Mid (L4): Two-loop O(n²); one-pass after hint.
  • Senior (L5): One-pass with skip + total check; proves lemma when asked.
  • Staff (L6): + prefix-min equivalence + bounded-tank deque extension.
  • Principal (L7+): + control-theory framing (Lyapunov function for “tank” stability) + LP duality (cut interpretation of the minimum prefix).

13. Follow-up Q&A

Q1: Multiple valid starts — return all? A1: All form a contiguous arc (proof from the lemma). Linear scan to find the arc bounds.

Q2: Tank has cap C? A2: At each step tank = min(C, tank + gas[i]) - cost[i]. Skip lemma weakens; sliding-window/monotonic-deque on prefixes works.

Q3: Variable cost depending on direction (forward vs reverse)? A3: Try both directions; same O(n) per direction.

Q4: Multiple vehicles starting simultaneously, each consuming from station gas? A4: Multi-agent scheduling; usually NP-hard in general; LP relaxation often used.

Q5: Prove total ≥ 0 ⟹ a valid start exists. A5: Let S = index of minimum running prefix sum. Starting at S+1 makes all prefixes non-negative (by rotation). Combined with total ≥ 0, the circular loop closes non-negatively.

14. Solution Walkthrough

See solution.py:

  • can_complete_circuit — one-pass O(n) skip greedy.
  • can_complete_circuit_prefix_min — O(n) via min-prefix identity.
  • can_complete_circuit_brute — try each start; O(n²) oracle.

15. Beyond the Problem

Principal code review: “Gas Station is the cleanest example of a monotone failure-skip invariant: once a prefix fails, an entire region is eliminated. This pattern reappears in: TCP slow-start / congestion control (once you hit packet loss, an entire window is invalidated and we restart at a known good point), JIT deoptimization (once a speculative assumption fails at PC=i, every speculation rooted in the chain is invalidated and we rebase at the next safe IR boundary), and Paxos prepare-reject (once a higher proposal is observed, all in-flight lower proposals are doomed — the proposer skips ahead). At Staff+, the meta-lesson is: invariants that monotonically eliminate future work are the most powerful tools in algorithm and systems design. They turn O(n²) into O(n), turn quadratic congestion control into linear, and turn distributed consensus from impossible into terminating. The exam question is: when you face an O(n²) brute, is there an invariant — usually expressible as ‘if X fails at i, no j ∈ [start, i] succeeds’ — that lets you skip?”