‹ DS&A interview · Socratic
DSA · Greedy · #78

Gas Station

Module 51 · difficulty 3/5·⏱ 30:00starts on first keystroke

There are `n` gas stations arranged in a circle. `gas[i]` is the amount of gas available at station `i`, and `cost[i]` is the gas needed to travel from station `i` to station `i + 1` (the next station, wrapping around). You start with an empty tank at one of the stations and drive clockwise. Implement `canCompleteCircuit(gas, cost)` that returns the index of the starting station from which you can travel all the way around the circuit exactly once, or `-1` if no such start exists. The answer is guaranteed to be unique when it exists.

Examples
  • gas = [1,2,3,4,5], cost = [3,4,5,1,2] → 3 — Start at index 3: tank fills to 4, drives to 4 (4-1=3 left), +5=8 then -2=6 to index 0, +1=7 then -3=4, +2=6 then -4=2, +3=5 then -5=0 back to 3.
  • gas = [2,3,4], cost = [3,4,3] → -1 — Total gas (9) < total cost (10), so the circuit can never be completed.
  • gas = [5], cost = [4] → 0 — Single station: 5 gas covers the 4 cost to loop back to itself.
Constraints
  • · n == gas.length == cost.length
  • · 1 <= n <= 10^5
  • · 0 <= gas[i], cost[i] <= 10^4
  • · If a valid start exists it is unique.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.