Stage 1 · Code
Greedy Algorithms
Gas Station
Circuit completion with gas and cost arrays.
6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Problem
N gas stations in circle. gas[i] = fuel at station i. cost[i] = fuel to reach station (i+1)%N. Start with empty tank at some station. Find starting station index that completes circuit, or -1 if impossible.
Greedy Insight
If total gas < total cost, impossible. Otherwise, solution exists. Key: if we fail starting at i (tank < 0 at station k), then no station between i and k can be valid start. Because tank was non-negative from i to k-1, so starting later would have even less fuel. Next candidate: k+1.
Implementation
Gogas-station-circuit.go
22 linesLn 1, Col 1Go
Track total surplus/deficit. If currTank negative, reset start to i+1 and reset currTank. Total tank must be ≥ 0 for solution to exist. O(n) time, O(1) space.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.