Loading…

mediumStack QueueFrequently asked

Truck Tour

Q: How do you solve Truck Tour using the Brute Force — Simulate From Every Start approach?

When to use it: Mention to frame the problem and the feasibility check, then note O(n²) times out at n = 10⁵. Try every pump as a potential start. For candidate `s`, simulate the circular tour: set the tank to 0 and, for each of the `n` steps, add `petrol[(s+j) mod n] − distance[(s+j) mod n]`. If the tank ever goes negative, `s` fails; if it survives all `n` steps, `s` is the answer. **Why it's the natural first attempt.** It's the literal definition of 'valid start'. No insight needed — just simulate each candidate fully. **Why it's too slow.** Each simulation is O(n) and there are n candidates, giving O(n²). At n = 10⁵ that's ~10¹⁰ operations and a guaranteed timeout. The brute force is valuable only as a correctness oracle for the greedy on small inputs. Time complexity: O(n²). Space complexity: O(1).

Q: How do you solve Truck Tour using the Greedy Single Pass (Optimal) approach?

When to use it: The intended solution. Lead with the skip lemma and the total ≥ 0 feasibility guarantee. Walk the pumps once, maintaining two running sums: a global `total` of net fuel across all pumps, and a local `tank` measuring net fuel since the current candidate start. **The reset rule.** At pump `i`, add `diff = petrol[i] − distance[i]` to both. If `tank` becomes negative, the truck couldn't reach pump `i+1` starting from the current candidate. Set `start = i + 1` and reset `tank = 0`. **Why we can skip every start in the failing block (the key lemma).** Say the candidate start is `s` and the tank first goes negative at pump `i`. For any pump `m` with `s < m ≤ i`, the tank was non-negative when we arrived at `m` (otherwise we'd have reset earlier). That means the fuel accumulated from `s` to `m−1` was `≥ 0`. So starting at `m` instead of `s` gives *no more* fuel reaching pump `i` — in fact less or equal — and would also fail by `i`. Hence none of `s..i` can be a valid start, and we jump straight to `i+1`. This is what turns O(n²) into O(n): each pump is examined once and never reconsidered as part of a failed block. **Why `total ≥ 0` certifies the answer.** `total` is the net fuel over the entire circle. If `total ≥ 0`, a valid start must exist, and a classic result guarantees the single candidate surviving the pass is it — once you can reach the end of the array from `start` without going negative, the wrap-around (the part before `start`) is covered because the deficit there is exactly offset by the surplus after `start` (their sum is `total ≥ 0`). So we don't need to simulate the wrap explicitly. **Why reset only `tank`, not `total`.** `tank` is local to the current candidate and must restart at each new candidate. `total` measures global feasibility across all pumps and must accumulate uninterrupted. Time complexity: O(n). Space complexity: O(1).

Stack & Queue · 15 of 17 · 9 min

A truck must complete a circular tour of n petrol pumps. Pump i gives petrol[i] units of fuel, and the distance from pump i to the next pump (pump (i+1) mod n) costs distance[i] units of fuel (1 unit per km). The truck has an unlimited tank and starts empty.

Find the index of the first petrol pump from which the truck can start and complete the full circular tour, returning to the start. It is guaranteed that a unique solution exists.

In plain English

Crossing from pump i to the next nets `petrol[i] − distance[i]` fuel. A start is valid if, beginning there with an empty tank and going around the circle, the running fuel never dips below zero. Because a valid start is guaranteed, the only question is *which* index — and a single greedy pass finds it.

Examples

Example 1

Input: petrolpumps = [[1, 5], [10, 3], [3, 4]]
Output: 1
Note: Start at pump 0: tank 1−5 = −4 < 0, fail. Reset start to 1. From pump 1: 10−3=7, then 3−4=−1 → tank 6, then 1−5=−4 → tank 2; survives the loop. Answer 1.

Example 2

Input: petrolpumps = [[4, 6], [6, 5], [7, 3], [4, 5]]
Output: 1
Note: Pump 0 fails (4−6=−2). From pump 1: 1, 5, 4, then wrap 4−6=−2 → 2 ≥ 0 throughout. Start 1.

Example 3

Input: petrolpumps = [[5, 1], [2, 3], [1, 2], [3, 1]]
Output: 0
Note: From pump 0: 4, 3, 2, 4 — never negative. Start 0 works.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ petrol[i], distance[i] ≤ 10⁹
A valid starting pump is guaranteed to exist (total petrol ≥ total distance)
An O(n²) simulation times out — aim for O(n)

Clarifying questions4First question: Is a valid start guaranteed, or must I detect impossibility?Explore questions

Q1.Is a valid start guaranteed, or must I detect impossibility?
This problem guarantees one exists (total petrol ≥ total distance). The general Gas Station variant returns −1 when total < 0.
Q2.Is the route circular?
Yes — after the last pump you return toward pump 0. The greedy avoids explicit wrap simulation because total ≥ 0 certifies the wrap closes.
Q3.Can there be more than one valid start?
The problem states a unique solution. The greedy returns that single start.
Q4.What does negative running fuel mean?
The truck ran out before reaching a pump — that candidate start (and everything from it up to the failure point) is invalid.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

A unique valid start exists when total petrol ≥ total distance. Find it in one pass: track a running tank from a candidate start; the moment it goes negative at pump i, no start in [candidate..i] can work, so jump the candidate to i+1 and reset the tank. The last surviving candidate is the answer — O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you find the O(n) greedy instead of trying every start (O(n²)), and can justify why a failing prefix lets you skip all starts within it.

Where candidates slip

Trying every starting pump with a full simulation (O(n²) → TLE), or resetting the global total when the local tank goes negative.

How to stand out

Prove the skip lemma (if start s fails at i, no s..i works), state the total ≥ 0 feasibility condition, and note this is the same prefix-reset logic as Kadane and Gas Station.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Simulate From Every Start	`O(n²)`	`O(1)`	Mention to frame the problem and the feasibility check, then note O(n²) times out at n = 10⁵.	Read
2	Greedy Single Pass (Optimal)Optimal	`O(n)`	`O(1)`	The intended solution. Lead with the skip lemma and the total ≥ 0 feasibility guarantee.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewstart=0, tank=0, total=0tank < 0?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Simulate From Every Start

TimeO(n²)SpaceO(1)

Mention to frame the problem and the feasibility check, then note O(n²) times out at n = 10⁵.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The definition is direct: try each pump as the start and simulate the whole loop, checking the tank never goes negative.

2Hint 2Explore hint

For start s, walk all n pumps in circular order accumulating petrol − distance; if it stays ≥ 0 the whole way, s is the answer.

3Hint 3Explore hint

Each start costs O(n) to simulate and there are n starts → O(n²). For n = 10⁵ that's 10¹⁰ — too slow.

A · Core idea

Try every pump as a potential start. For candidate s, simulate the circular tour: set the tank to 0 and, for each of the n steps, add petrol[(s+j) mod n] − distance[(s+j) mod n]. If the tank ever goes negative, s fails; if it survives all n steps, s is the answer.

Why it's the natural first attempt. It's the literal definition of 'valid start'. No insight needed — just simulate each candidate fully.

Why it's too slow. Each simulation is O(n) and there are n candidates, giving O(n²). At n = 10⁵ that's ~10¹⁰ operations and a guaranteed timeout. The brute force is valuable only as a correctness oracle for the greedy on small inputs.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

petrolpumps = [[1, 5], [10, 3], [3, 4]]

Array state

start 0

tank 1-5 = -4 → fail

1/5

[0]

10/3

[1]

3/4

[2]

Current pointerResolved stateNot processed

Final result1

C · Code with teaching comments

Reference implementation previewpublic int truckTourBrute(int[][] pumps) { int n = pumps.length; for (int s = 0; s < n; s++) { long tank = 0; boolean ok = true;Explore the full code

solution.javaJava

Brute Force — Simulate From Every Start — reference

4 teaching notes

1
public int truckTourBrute(int[][] pumps) {
2
    int n = pumps.length;
3
    // Try every pump as the starting point.
4
    for (int s = 0; s < n; s++) {
5
        long tank = 0;
6
        boolean ok = true;
7
        for (int j = 0; j < n; j++) {
8
            // Circular index so the tour wraps past the last pump.
9
            int idx = (s + j) % n;
10
            // Net fuel after crossing this pump; long avoids overflow.
11
            tank += (long) pumps[idx][0] - pumps[idx][1];
12
            if (tank < 0) {
13
                ok = false;
14
                break;
15
            }
16
        }
17
        if (ok) {
18
            return s;
19
        }
20
    }
21
    return -1;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Brute force re-simulates overlapping prefixes from scratch. The greedy's leap is realising that a prefix which fails at pump i rules out every start within it at once — so we never need to retry those.

ComplexityO(n²) time, O(1) space — n candidate starts, each requiring an O(n) circular simulation → O(n²) time. Only a few counters → O(1) space.

E · Edge cases and pitfalls4single pump with petrol ≥ distance — Start 0 trivially completes; returns 0.Explore edge cases

Edge cases handled

single pump with petrol ≥ distanceStart 0 trivially completes; returns 0.

Pitfalls

O(n²) re-simulation times out for n = 10⁵.
Forgetting the modulo wrap, so the circular tour isn't actually circular.
Integer overflow if petrol/distance are summed in 32-bit — use long.

03.2

Approach 2 of 2 · Optimal

Greedy Single Pass (Optimal)

TimeO(n)SpaceO(1)

The intended solution. Lead with the skip lemma and the total ≥ 0 feasibility guarantee.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Suppose starting at s you run dry reaching pump i. Could any pump strictly between s and i be a better start?

2Hint 2Explore hint

No — each of those pumps was reached with a non-negative tank from s, so starting there gives even less fuel and also fails by i. So jump the candidate start to i+1.

3Hint 3Explore hint

Track a global total of (petrol − distance). If total ≥ 0 a start exists, and the candidate left standing after one pass is it.

A · Core idea

Walk the pumps once, maintaining two running sums: a global total of net fuel across all pumps, and a local tank measuring net fuel since the current candidate start.

The reset rule. At pump i, add diff = petrol[i] − distance[i] to both. If tank becomes negative, the truck couldn't reach pump i+1 starting from the current candidate. Set start = i + 1 and reset tank = 0.

Why we can skip every start in the failing block (the key lemma). Say the candidate start is s and the tank first goes negative at pump i. For any pump m with s < m ≤ i, the tank was non-negative when we arrived at m (otherwise we'd have reset earlier). That means the fuel accumulated from s to m−1 was ≥ 0. So starting at m instead of s gives no more fuel reaching pump i — in fact less or equal — and would also fail by i. Hence none of s..i can be a valid start, and we jump straight to i+1. This is what turns O(n²) into O(n): each pump is examined once and never reconsidered as part of a failed block.

Why `total ≥ 0` certifies the answer. total is the net fuel over the entire circle. If total ≥ 0, a valid start must exist, and a classic result guarantees the single candidate surviving the pass is it — once you can reach the end of the array from start without going negative, the wrap-around (the part before start) is covered because the deficit there is exactly offset by the surplus after start (their sum is total ≥ 0). So we don't need to simulate the wrap explicitly.

Why reset only `tank`, not `total`. tank is local to the current candidate and must restart at each new candidate. total measures global feasibility across all pumps and must accumulate uninterrupted.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

petrolpumps = [[1, 5], [10, 3], [3, 4]]

Array state

i=0

tank = -4 < 0 → start = 1, tank = 0

-4

[0]

start ↓

[1]

-1

[2]

Current pointerResolved stateNot processed

Final result1

C · Code with teaching comments

solution.javaJava

Greedy Single Pass (Optimal) — optimal

6 teaching notes

1
public int truckTour(int[][] pumps) {
2
    int n = pumps.length;
3
    long total = 0;
4
    long tank = 0;
5
    int start = 0;
6
    for (int i = 0; i < n; i++) {
7
        // Net fuel crossing pump i; cast to long since values reach 10⁹.
8
        long diff = (long) pumps[i][0] - pumps[i][1];
9
        // Global net fuel — its sign decides whether ANY start works.
10
        total += diff;
11
        // Net fuel since the current candidate start.
12
        tank += diff;
13
        // Candidate fails reaching pump i+1.
14
        if (tank < 0) {
15
            start = i + 1;
16
            tank = 0;
17
        }
18
    }
19
    // total ≥ 0 guarantees the surviving candidate is valid.
20
    return total >= 0 ? start : -1;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

This is the same prefix-reset reasoning as Kadane's maximum-subarray: a running sum that goes negative can't help any future start, so discard it and begin fresh. Recognising 'negative prefix ⇒ reset the start' lets you collapse a quadratic search to a single linear scan.

ComplexityO(n) time, O(1) space — A single sweep over n pumps with constant work each → O(n) time. A handful of counters → O(1) space.

E · Edge cases and pitfalls6all pumps have petrol ≥ distance — tank never goes negative; start stays 0.Explore edge cases

Edge cases handled

all pumps have petrol ≥ distancetank never goes negative; start stays 0.
valid start is the last pumpEvery earlier prefix fails and resets, leaving start = n−1.

Pitfalls

Resetting total along with tank — total must measure global feasibility uninterrupted.
Returning start without verifying total ≥ 0 in the general (impossible-allowed) variant.
32-bit overflow on sums of values up to 10⁹ — use long/64-bit.
Setting start = i instead of i + 1 — the failing pump i can't be the start either.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int truckTour(int[][] pumps) { int n = pumps.length; long total = 0; long tank = 0; int start = 0;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Resetting the global total on failure

total tracks whether ANY start can complete the loop and must accumulate across all pumps. Resetting it when the local tank dips negative destroys the feasibility test and can return a wrong start.

Explore the code comparison

Don't write this

if tank < 0:
    start = i + 1
    tank = 0
    total = 0   # wrong: loses the global feasibility sum

Write this instead

if tank < 0:
    start = i + 1
    tank = 0
# total keeps accumulating

Advancing the start to i instead of i + 1

If the tank went negative at pump i, then pump i itself cannot be a valid start (you can't even leave it with enough fuel). The next viable candidate begins at i + 1.

Explore the code comparison

Don't write this

if (tank < 0) {
    start = i;      // pump i also fails
    tank = 0;
}

Write this instead

if (tank < 0) {
    start = i + 1;
    tank = 0;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy single pass: reset start when running balance dips below zero

Code pattern to memorize

total = 0; tank = 0; start = 0
for i in range(n):
    diff = petrol[i] - distance[i]
    total += diff
    tank += diff
    if tank < 0:
        start = i + 1
        tank = 0
return start   # guaranteed valid since total >= 0

Rules to remember

1If tank (running balance from the current candidate) drops below 0 at pump i, no pump in [start..i] is a valid start — move start = i + 1 and reset tank = 0.
2Keep a separate total over all pumps; the tour is feasible iff total ≥ 0, and then the found start is the unique answer.
3diff = petrol[i] − distance[i] is the net fuel gained crossing pump i to the next.
4Reset only the local tank, never total — total verifies global feasibility.
5Single pass, no need to simulate the wrap-around explicitly once you know total ≥ 0.

Use this pattern when

Circular route 'where can I start to complete the loop?' (gas station) problems
Find a starting index so a running prefix balance never goes negative
Any cyclic resource problem with gains and costs per step and a feasibility guarantee
Maximum-subarray-like reasoning where a negative running sum should reset

Choose another pattern when

Multiple valid starts must all be returned → this greedy gives one; enumerate differently
No feasibility guarantee and you must detect impossibility → also check total < 0 → return -1
Costs depend on the path taken, not fixed per edge → greedy prefix reset no longer applies

Interview takeaway

The gas-station insight: if you run out of fuel reaching pump i from start s, then every pump between s and i is also a doomed start, so skip straight to i+1. One pass finds the unique start whenever total petrol ≥ total distance.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternGreedy prefix-reset on a circular array: a prefix that goes negative eliminates every start within it, so jump past it. Feasibility is total ≥ 0. Shares its core with Kadane's maximum subarray and Gas Station.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Gas Station
Coming soon
Same greedy; return −1 when total < 0 since a valid start may not exist.
Maximum Subarray
Coming soon
Kadane uses the same 'reset when the running sum goes negative' prefix logic.
Circular Array Loop
Coming soon
Another circular-traversal problem; uses fast/slow pointers on a ring.

Same pattern

←

Simple Text Editor

Continue · Next problem

Waiter

mediumStack QueueFrequently asked

Truck Tour

Stack & Queue · 15 of 17 · 9 min

Find the index of the first petrol pump from which the truck can start and complete the full circular tour, returning to the start. It is guaranteed that a unique solution exists.

In plain English

Examples

Example 1

Input: petrolpumps = [[1, 5], [10, 3], [3, 4]]
Output: 1
Note: Start at pump 0: tank 1−5 = −4 < 0, fail. Reset start to 1. From pump 1: 10−3=7, then 3−4=−1 → tank 6, then 1−5=−4 → tank 2; survives the loop. Answer 1.

Example 2

Input: petrolpumps = [[4, 6], [6, 5], [7, 3], [4, 5]]
Output: 1
Note: Pump 0 fails (4−6=−2). From pump 1: 1, 5, 4, then wrap 4−6=−2 → 2 ≥ 0 throughout. Start 1.

Example 3

Input: petrolpumps = [[5, 1], [2, 3], [1, 2], [3, 1]]
Output: 0
Note: From pump 0: 4, 3, 2, 4 — never negative. Start 0 works.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ petrol[i], distance[i] ≤ 10⁹
A valid starting pump is guaranteed to exist (total petrol ≥ total distance)
An O(n²) simulation times out — aim for O(n)

Clarifying questions4First question: Is a valid start guaranteed, or must I detect impossibility?Explore questions

Q1.Is a valid start guaranteed, or must I detect impossibility?
This problem guarantees one exists (total petrol ≥ total distance). The general Gas Station variant returns −1 when total < 0.
Q2.Is the route circular?
Yes — after the last pump you return toward pump 0. The greedy avoids explicit wrap simulation because total ≥ 0 certifies the wrap closes.
Q3.Can there be more than one valid start?
The problem states a unique solution. The greedy returns that single start.
Q4.What does negative running fuel mean?
The truck ran out before reaching a pump — that candidate start (and everything from it up to the failure point) is invalid.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you find the O(n) greedy instead of trying every start (O(n²)), and can justify why a failing prefix lets you skip all starts within it.

Where candidates slip

Trying every starting pump with a full simulation (O(n²) → TLE), or resetting the global total when the local tank goes negative.

How to stand out

Prove the skip lemma (if start s fails at i, no s..i works), state the total ≥ 0 feasibility condition, and note this is the same prefix-reset logic as Kadane and Gas Station.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Simulate From Every Start	`O(n²)`	`O(1)`	Mention to frame the problem and the feasibility check, then note O(n²) times out at n = 10⁵.	Read
2	Greedy Single Pass (Optimal)Optimal	`O(n)`	`O(1)`	The intended solution. Lead with the skip lemma and the total ≥ 0 feasibility guarantee.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Simulate From Every Start

TimeO(n²)SpaceO(1)

Mention to frame the problem and the feasibility check, then note O(n²) times out at n = 10⁵.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The definition is direct: try each pump as the start and simulate the whole loop, checking the tank never goes negative.

2Hint 2Explore hint

For start s, walk all n pumps in circular order accumulating petrol − distance; if it stays ≥ 0 the whole way, s is the answer.

3Hint 3Explore hint

Each start costs O(n) to simulate and there are n starts → O(n²). For n = 10⁵ that's 10¹⁰ — too slow.

A · Core idea

Why it's the natural first attempt. It's the literal definition of 'valid start'. No insight needed — just simulate each candidate fully.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

petrolpumps = [[1, 5], [10, 3], [3, 4]]

Array state

start 0

tank 1-5 = -4 → fail

1/5

[0]

10/3

[1]

3/4

[2]

Current pointerResolved stateNot processed

Final result1

C · Code with teaching comments

Reference implementation previewpublic int truckTourBrute(int[][] pumps) { int n = pumps.length; for (int s = 0; s < n; s++) { long tank = 0; boolean ok = true;Explore the full code

solution.javaJava

Brute Force — Simulate From Every Start — reference

4 teaching notes

1
public int truckTourBrute(int[][] pumps) {
2
    int n = pumps.length;
3
    // Try every pump as the starting point.
4
    for (int s = 0; s < n; s++) {
5
        long tank = 0;
6
        boolean ok = true;
7
        for (int j = 0; j < n; j++) {
8
            // Circular index so the tour wraps past the last pump.
9
            int idx = (s + j) % n;
10
            // Net fuel after crossing this pump; long avoids overflow.
11
            tank += (long) pumps[idx][0] - pumps[idx][1];
12
            if (tank < 0) {
13
                ok = false;
14
                break;
15
            }
16
        }
17
        if (ok) {
18
            return s;
19
        }
20
    }
21
    return -1;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — n candidate starts, each requiring an O(n) circular simulation → O(n²) time. Only a few counters → O(1) space.

E · Edge cases and pitfalls4single pump with petrol ≥ distance — Start 0 trivially completes; returns 0.Explore edge cases

Edge cases handled

single pump with petrol ≥ distanceStart 0 trivially completes; returns 0.

Pitfalls

O(n²) re-simulation times out for n = 10⁵.
Forgetting the modulo wrap, so the circular tour isn't actually circular.
Integer overflow if petrol/distance are summed in 32-bit — use long.

03.2

Approach 2 of 2 · Optimal

Greedy Single Pass (Optimal)

TimeO(n)SpaceO(1)

The intended solution. Lead with the skip lemma and the total ≥ 0 feasibility guarantee.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Suppose starting at s you run dry reaching pump i. Could any pump strictly between s and i be a better start?

2Hint 2Explore hint

No — each of those pumps was reached with a non-negative tank from s, so starting there gives even less fuel and also fails by i. So jump the candidate start to i+1.

3Hint 3Explore hint

Track a global total of (petrol − distance). If total ≥ 0 a start exists, and the candidate left standing after one pass is it.

A · Core idea

Walk the pumps once, maintaining two running sums: a global total of net fuel across all pumps, and a local tank measuring net fuel since the current candidate start.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

petrolpumps = [[1, 5], [10, 3], [3, 4]]

Array state

i=0

tank = -4 < 0 → start = 1, tank = 0

-4

[0]

start ↓

[1]

-1

[2]

Current pointerResolved stateNot processed

Final result1

C · Code with teaching comments

solution.javaJava

Greedy Single Pass (Optimal) — optimal

6 teaching notes

1
public int truckTour(int[][] pumps) {
2
    int n = pumps.length;
3
    long total = 0;
4
    long tank = 0;
5
    int start = 0;
6
    for (int i = 0; i < n; i++) {
7
        // Net fuel crossing pump i; cast to long since values reach 10⁹.
8
        long diff = (long) pumps[i][0] - pumps[i][1];
9
        // Global net fuel — its sign decides whether ANY start works.
10
        total += diff;
11
        // Net fuel since the current candidate start.
12
        tank += diff;
13
        // Candidate fails reaching pump i+1.
14
        if (tank < 0) {
15
            start = i + 1;
16
            tank = 0;
17
        }
18
    }
19
    // total ≥ 0 guarantees the surviving candidate is valid.
20
    return total >= 0 ? start : -1;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — A single sweep over n pumps with constant work each → O(n) time. A handful of counters → O(1) space.

E · Edge cases and pitfalls6all pumps have petrol ≥ distance — tank never goes negative; start stays 0.Explore edge cases

Edge cases handled

all pumps have petrol ≥ distancetank never goes negative; start stays 0.
valid start is the last pumpEvery earlier prefix fails and resets, leaving start = n−1.

Pitfalls

Resetting total along with tank — total must measure global feasibility uninterrupted.
Returning start without verifying total ≥ 0 in the general (impossible-allowed) variant.
32-bit overflow on sums of values up to 10⁹ — use long/64-bit.
Setting start = i instead of i + 1 — the failing pump i can't be the start either.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int truckTour(int[][] pumps) { int n = pumps.length; long total = 0; long tank = 0; int start = 0;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Resetting the global total on failure

total tracks whether ANY start can complete the loop and must accumulate across all pumps. Resetting it when the local tank dips negative destroys the feasibility test and can return a wrong start.

Explore the code comparison

Don't write this

if tank < 0:
    start = i + 1
    tank = 0
    total = 0   # wrong: loses the global feasibility sum

Write this instead

if tank < 0:
    start = i + 1
    tank = 0
# total keeps accumulating

Advancing the start to i instead of i + 1

If the tank went negative at pump i, then pump i itself cannot be a valid start (you can't even leave it with enough fuel). The next viable candidate begins at i + 1.

Explore the code comparison

Don't write this

if (tank < 0) {
    start = i;      // pump i also fails
    tank = 0;
}

Write this instead

if (tank < 0) {
    start = i + 1;
    tank = 0;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy single pass: reset start when running balance dips below zero

Code pattern to memorize

total = 0; tank = 0; start = 0
for i in range(n):
    diff = petrol[i] - distance[i]
    total += diff
    tank += diff
    if tank < 0:
        start = i + 1
        tank = 0
return start   # guaranteed valid since total >= 0

Rules to remember

1If tank (running balance from the current candidate) drops below 0 at pump i, no pump in [start..i] is a valid start — move start = i + 1 and reset tank = 0.
2Keep a separate total over all pumps; the tour is feasible iff total ≥ 0, and then the found start is the unique answer.
3diff = petrol[i] − distance[i] is the net fuel gained crossing pump i to the next.
4Reset only the local tank, never total — total verifies global feasibility.
5Single pass, no need to simulate the wrap-around explicitly once you know total ≥ 0.

Use this pattern when

Circular route 'where can I start to complete the loop?' (gas station) problems
Find a starting index so a running prefix balance never goes negative
Any cyclic resource problem with gains and costs per step and a feasibility guarantee
Maximum-subarray-like reasoning where a negative running sum should reset

Choose another pattern when

Multiple valid starts must all be returned → this greedy gives one; enumerate differently
No feasibility guarantee and you must detect impossibility → also check total < 0 → return -1
Costs depend on the path taken, not fixed per edge → greedy prefix reset no longer applies

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Gas Station
Coming soon
Same greedy; return −1 when total < 0 since a valid start may not exist.
Maximum Subarray
Coming soon
Kadane uses the same 'reset when the running sum goes negative' prefix logic.
Circular Array Loop
Coming soon
Another circular-traversal problem; uses fast/slow pointers on a ring.

Same pattern

←

Simple Text Editor

Continue · Next problem

Waiter