Reset-on-negative sweep

40 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Five petrol stations sit on a circular road. At station i you get gas[i] litres, and driving to the next station burns cost[i] litres. With gas [1, 2, 3, 4, 5] and cost [3, 4, 5, 1, 2], from which station can you start with an empty tank and drive the whole loop?

By hand you would try each start. Start at 0: get 1, need 3, stranded. Start at 1: get 2, need 4, stranded. Start at 3: get 4, pay 1, tank 3; get 5, pay 2, tank 6; get 1, pay 3, tank 4; get 2, pay 4, tank 2; get 3, pay 5, tank 0. Made it. For n stations that is n starts times up to n stops each: O(n²), about 10 billion steps for 100,000 stations.

Build the structure, one piece at a time

Think of each station as a single number, its gain: gas[i] − cost[i]. Here the gains are [−2, −2, −2, 3, 3]. Driving from a start is just adding gains in order, and you are stranded the first time the running sum goes below zero. Two counters do all the work:

• total: the sum of all gains, never reset.
• tank: the running sum since the current candidate start; when it goes negative, reset it to 0 and move the candidate start to the next station.

1. i = 0: tank = −2. Negative. Start cannot be 0; candidate = 1, tank = 0.
2. i = 1: tank = −2. Negative. Candidate = 2, tank = 0.
3. i = 2: tank = −2. Negative. Candidate = 3, tank = 0.
4. i = 3: tank = 3.
5. i = 4: tank = 6.

total = −2 − 2 − 2 + 3 + 3 = 0, which is not negative, so a full loop is possible, and the answer is the last candidate, station 3. One pass, no restarts of the drive itself.

Why it is correct

Two facts. First, if you start at s and first go negative at station k, then no station between s and k can be a valid start either. Starting later in that stretch only removes some non-negative prefix of gains (the tank was at least 0 at every station before k), so you arrive at k with less fuel than before, and you were already stranded there. That justifies jumping the candidate straight to k + 1. Second, if the total of all gains is at least 0, the final candidate works: every earlier stretch was abandoned because its sum was negative, so the stretch from the final candidate to the end has sum ≥ 0 at every point (it never went negative) and large enough to cover the negative stretches at the beginning when you wrap around, since the grand total is ≥ 0.

Σ gains over the loop ≥ 0 ⇔ some start completes the loop

Why it is fast

One scan with two additions and one comparison per station: O(n) time, O(1) memory. For 100,000 stations that is 100,000 steps rather than 10 billion. The saving comes from the first fact: a failed attempt rules out a whole stretch of starts at once instead of one.

How to recognise it in an interview

Cues: a circular route, a running balance that must never dip below zero, "find a starting point". The same reset-on-negative move is the heart of Kadane's algorithm for the maximum subarray, where a negative running sum is dropped because it can only hurt what follows. Say: I will track a running sum and restart whenever it goes negative, and use the grand total to decide whether any answer exists. Gas Station is the example. Minimum Value to Get Positive Step by Step Sum is the same scan asking how low the running sum ever gets. Maximum Subarray is the Kadane cousin.

02The idea in one line

Walk once; whenever the running tank goes negative, restart from the next index.

Reach for it when: Gas station, max subarray (Kadane cousin), minimum start value.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Gas Station gas [1,2,3,4,5] cost [3,4,5,1,2]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Walk once; tank resets when it drops below zero, total never resets
2. i=0: tank = -2 < 0, nothing before 1 can be the start; restart at 1
3. i=1: tank = -2 < 0, nothing before 2 can be the start; restart at 2
4. i=2: tank = -2 < 0, nothing before 3 can be the start; restart at 3
5. i=3: tank +0 +3 = 3, still ≥ 0
6. i=4: tank +3 +3 = 6, still ≥ 0
7. total = 0 ≥ 0, so a tour exists; the last restart 3 is the answer
8. One pass, two counters: O(n) time, O(1) space

04Asked at Google

4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Greedy: Furthest reach (jump game), Sort, then take greedily, Last-occurrence partition, Two-pass neighbour constraints, Counting-based greedy (small alphabet), Two-pointer assignment after sorting.