Queue • Optimization

Circular Tour / Gas Station

Given a circular route with petrol pumps, find the starting pump from which the truck can complete the entire circle without running out of petrol.

Try Interactive Simulator

The Logic

If we start at `A` and run out of gas before reaching `B`, it means NO station between `A` and `B` can be a valid starting point either! So our next potential start is `B+1`.

Queue Tie-in

This problem is often solved natively using a Queue by enqueuing and dequeuing stations. However, the optimized O(N) O(1) approach presented here conceptually slides a window over the route without actually needing queue memory.

Total Deficit

We keep track of the gas deficit generated by failed starting points. At the very end, if the gas left in the tank covers the historical deficit, a tour is possible.

START

+ 4- 6

Stat 0

START

+ 6- 5

Stat 1

START

+ 7- 3

Stat 2

START

+ 4- 5

Stat 3

Current Tank0

Total Deficit0

Code Tracker

:::

1let start = 0, tank = 0, totalDeficit = 0;

2for (let i = 0; i < N; i++) {

3 tank += petrol[i] - distance[i];

4 if (tank < 0) {

5 start = i + 1;

6 totalDeficit += tank;

7 tank = 0;

8 }

9}

10return (tank + totalDeficit >= 0) ? start : -1;