Gas Station

Gas Station

What is this problem about?

The Gas Station interview question is a classic problem involving a circular route. You have n gas stations, each providing a certain amount of gas[i]. Traveling to the next station costs cost[i] gas. You start with an empty tank. You need to find the starting gas station's index from which you can travel around the entire circuit once in a clockwise direction. If no such starting point exists, return -1. There is guaranteed to be at most one unique solution.

Why is this asked in interviews?

This is an extremely popular Greedy interview pattern problem asked by almost every major tech company, including Google, Amazon, and Meta. It tests a candidate's ability to optimize an $O(N^2)$ brute-force check into an elegant $O(N)$ single-pass solution. It evaluates mathematical intuition: realizing that if you fail to reach station $B$ starting from station $A$, you will also fail starting from any station between $A$ and $B$.

Algorithmic pattern used

This problem relies on a Greedy Single-Pass pattern.

1. Global Check: Calculate the total_gas and total_cost. If total_gas < total_cost, it's mathematically impossible to complete the circuit, so return -1 immediately.
2. Local Check: Iterate through the stations. Maintain a current_tank and a potential start_index (initially 0).
3. Add gas[i] - cost[i] to current_tank.
4. If current_tank < 0 at any point, it means you can't reach station $i+1$ from the current start_index.
5. Therefore, set start_index = i + 1 and reset current_tank = 0.
6. Return start_index.

Example explanation

gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]

• Total gas = 15, Total cost = 15. A solution exists.

1. Start at 0. Tank: $1 - 3 = -2$. Fails. Reset start to 1.
2. Start at 1. Tank: $2 - 4 = -2$. Fails. Reset start to 2.
3. Start at 2. Tank: $3 - 5 = -2$. Fails. Reset start to 3.
4. Start at 3. Tank: $4 - 1 = 3$. (Can proceed).
5. Reach 4. Tank: $3 + 5 - 2 = 6$. (Can proceed). Loop finishes. Start index 3 is valid.

Common mistakes candidates make

• Brute Force Simulation: Trying to simulate the journey from every single station, leading to $O(N^2)$ time complexity, which will time out for large inputs.
• Ignoring the Global Check: Forgetting to check if total_gas >= total_cost, which is the mathematical guarantee that the single-pass greedy logic will find a valid start.
• Complex Circular Logic: Trying to use modulo operators to wrap around the array during the greedy check, which is unnecessary if you rely on the global check.

Interview preparation tip

Memorize the proof for this greedy approach: If you start at A and your tank drops below zero just before reaching B, then starting at any station between A and B will drop below zero even earlier, because you would be starting with 0 gas instead of the positive gas you accumulated from A. Therefore, the next possible start is B.