Pattern Recognition Drill

#73 — Gas station

Medium Greedy

The Problem

Find starting station for a complete circuit, or -1 if impossible.

What approach would you use?

Think about it before scrolling down.

Key Signals

'Circular route' + 'enough gas?' → total gas >= total cost means solution exists
Track running surplus — when it goes negative, start must be after that point

Greedy

If total_gas >= total_cost, answer exists. Track running surplus; when < 0, reset start to next station. O(n).

Common Trap

Brute force trying every starting station is O(n²). The surplus reset insight gives O(n).

← #72 #74 →