Find the first circular tour that visits all Petrol Pumps

The problem, simply

Petrol pumps stand in a circle. Pump i gives petrol[i] litres, and it costs distance[i] litres to drive from pump i to the next pump. The truck starts empty, has an unlimited tank, and fills up fully at every pump it reaches.

Return the smallest index of a pump where the truck can start and drive the whole circle back to that pump. If no pump works, return -1.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every pump as the start and drive around.

1. For each start, set tank = 0.
2. Visit the n pumps from start, using (start + step) % n. Add petrol, take away distance.
3. If tank ever drops below 0, this start fails. If all n stretches are done, return start.

class Solution {
    public int tour(int[] petrol, int[] distance) {
        int n = petrol.length;
        for (int start = 0; start < n; start++) {
            int tank = 0;
            boolean ok = true;
            for (int step = 0; step < n; step++) {
                int i = (start + step) % n;           // wrap around the circle
                tank += petrol[i] - distance[i];
                if (tank < 0) { ok = false; break; }  // stuck on this stretch
            }
            if (ok) return start;
        }
        return -1;
    }
}

How long it takes: up to n starts, each driving up to n stretches, O(n^2). Extra room: O(1).

Way 2: the clever way

Two facts make one pass enough.

• Skip rule: if you start at s and get stuck on the stretch after pump i, then no pump from s to i can be the start. When you passed each of them, your tank was 0 or more, so starting there with an empty tank cannot do better.
• Total rule: if total petrol is at least total distance, some start works. If it is less, none does.

Think of the pumps in the current try as a waiting line, a queue. Each step adds the next pump at the back. When the tank goes below 0, the whole line is thrown out, and the next pump starts a new line.

1. Keep start = 0, tank = 0, total = 0.
2. For each pump i: add petrol[i] - distance[i] to both tank and total.
3. If tank < 0, set start = i + 1 and tank = 0.
4. At the end, return start if total >= 0, else -1.

class Solution {
    public int tour(int[] petrol, int[] distance) {
        int start = 0, tank = 0, total = 0;
        for (int i = 0; i < petrol.length; i++) {
            int gain = petrol[i] - distance[i];
            tank += gain;
            total += gain;
            if (tank < 0) {          // stuck: nobody from start to i can be the answer
                start = i + 1;
                tank = 0;
            }
        }
        return total >= 0 ? start : -1;
    }
}

How long it takes: one pass over the pumps, O(n). Extra room: three numbers, O(1).

Watch out for

• The total check is required. Without it, the loop can end with start pointing at a pump that does not work, or at n, which is not a pump at all.
• Arriving with exactly 0 is fine. Fail only when the tank goes below 0.
• Petrol is gained at a pump before the next stretch is driven, so add petrol[i] - distance[i] together in one step.
• The well known queue version that keeps front and rear pointers fails for one pump if rear starts at 1 without % n. Test n = 1.

What interviewers ask next

• Why does the total rule hold? Draw the running sum of petrol - distance. Start right after the place where it is lowest. From there, the sum never dips below where it began, so the tank never goes below 0.
• Is the answer unique? Not always, for example petrol = [2, 2], distance = [1, 1] works from both pumps. This method returns the smallest valid index, because every index before it was ruled out.
• What if the tank has a limit C? Then you cannot store everything, and the simple trick breaks. You need to simulate with the cap, or use more careful math.
• What if the truck can go both ways? Run the same pass on the reversed circle and take whichever works.
• This is LeetCode 134, Gas Station.

Remember this

Grown-up words: the friends with lemonade are petrol pumps, the one pass with restarts is a greedy algorithm, the running tank is a prefix sum, the pumps in the current try form a sliding queue, and the skip rule is the key lemma that makes it O(n).