Pattern Recognition Drill
Medium Greedy
The Problem
Given gas stations in a circle with gas[i] and cost[i], find the starting station to complete the circuit, or -1.
What approach would you use?
Think about it before scrolling down.
Track total and current tank. If current < 0, reset start to next station. If total >= 0, start is valid. O(n).
Common Trap
Don't simulate from each station O(nĀ²). The single-pass greedy works because if total >= 0, exactly one valid start exists.