Loading…

mediumGreedyLC #134Frequently asked

Gas Station

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

When to use it: Open with this to show you understand the mechanics of the circuit, then call out the O(n²) cost as the reason to look deeper. The most direct reading of the problem: pick a start, drive the full circle, and see if the tank ever goes negative. Repeat for every possible start and return the first one that survives the loop. **Why this is the natural first attempt.** The problem describes a physical simulation — pick up gas, pay to move on — so the literal solution is to *run* that simulation. With no insight required, you fix a start `s`, use `(s + k) % n` to wrap around the circle, and keep a running `tank`. The first `s` whose tank stays non-negative for all `n` hops is an answer. **Why the modular index matters.** The route is circular, so after the last station you must return to station 0. Using `(s + k) % n` for `k` from `0` to `n−1` visits every station exactly once *in driving order* starting from `s`, correctly modelling the wrap-around. Forgetting the modulo would simulate a straight line and miss the loop-closing cost. **Why we don't ship this.** Each candidate start triggers a full `n`-station simulation, so the worst case is `n × n = n²` work. For `n = 10⁵` that's up to 10¹⁰ operations — far too slow. Worse, it throws away information: when a simulation from `s` dies partway, the brute force restarts from `s+1` from scratch, even though the failed stretch already told us those starts are hopeless. That wasted insight is exactly what the greedy reclaims. Time complexity: O(n²). Space complexity: O(1).

LCPractice

Greedy Algorithms · 3 of 23 · 10 min

There are n gas stations along a circular route, where the amount of gas at the i-th station is gas[i].

You have a car with an unlimited gas tank, and it costs cost[i] of gas to travel from the i-th station to its next (i + 1)-th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

If there exists a solution, it is guaranteed to be unique.

In plain English

At each station you pick up gas[i] fuel and must pay cost[i] to reach the next station. Starting empty at some station, can you loop all the way around without the tank ever going negative? Return one valid starting index, or -1 if none exists. Only the net gas[i] − cost[i] per station matters.

Examples

Example 1

Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Note: Start at index 3: tank = 4. To 4: +5−1 = 8. To 0: +1−2 = 7. To 1: +2−3 = 6. To 2: +3−4 = 5. To 3: arrive with 5 ≥ 0 — full loop done.

Example 2

Input: gas = [2, 3, 4], cost = [3, 4, 3]
Output: -1
Note: Total gas 9 < total cost 10, so no starting station can complete the circuit.

Example 3

Input: gas = [5, 1, 2, 3, 4], cost = [4, 4, 1, 5, 1]
Output: 4
Note: Total gas 15 ≥ total cost 15, so a unique start exists; the sweep lands on index 4.

Constraints

n == gas.length == cost.length
1 ≤ n ≤ 10⁵
0 ≤ gas[i], cost[i] ≤ 10⁴
The answer is guaranteed to be unique if it exists

Clarifying questions4First question: Is the route truly circular — does the last station wrap back to the first?Explore questions

Q1.Is the route truly circular — does the last station wrap back to the first?
Yes. From station n−1 you pay cost[n−1] to return to station 0. That wrap-around is why a single linear scan needs justification.
Q2.Can the answer be ambiguous — multiple valid starts?
No, the problem guarantees a unique answer when one exists. That uniqueness is what lets us return the first surviving start without checking the rest.
Q3.What if total gas exactly equals total cost?
Then a solution exists (surplus is zero, which is allowed — the tank may touch but never drop below zero across the full loop).
Q4.Are gas and cost always non-negative?
Yes, both are in [0, 10⁴], so each net diff is in [−10⁴, 10⁴]. No tricks with negative fuel pickups.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Drive a circular route once, gaining gas[i] and spending cost[i] at each station. The brute force tries every start and simulates the loop in O(n²). The greedy does it in one pass: if total gas ≥ total cost a unique answer exists, and you find it by sweeping once — whenever your running tank dips below zero, the start can't be anywhere in the stretch you just covered, so reset start to the next station. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you separate the two questions — does a solution exist (a global sum check) versus where does it start (a local sweep) — and whether you can argue why a single left-to-right pass with a reset is enough rather than re-simulating every candidate.

Where candidates slip

Simulating from every start (O(n²)), or in the greedy resetting the tank but forgetting that the global `sum(gas) >= sum(cost)` check is what licenses returning the surviving start without re-wrapping.

How to stand out

Present the O(n²) simulation first, then split the problem: prove existence with the total comparison, and prove the start with the contradiction argument — if the tank dies at i starting from s, no station in [s, i] can be the answer.

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)`	Open with this to show you understand the mechanics of the circuit, then call out the O(n²) cost as the reason to look deeper.	Read
2	Greedy — Total Check + Reset On Deficit (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'two separate questions: does a start exist, and where is it' — then justify the reset with the contradiction argument.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewFind a start that completes the loopHow to find the start?Try every startOptimalExplore 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)

Open with this to show you understand the mechanics of the circuit, then call out the O(n²) cost as the reason to look deeper.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you fix a starting station s, you can just drive: add gas[i] − cost[i] as you go and watch whether the tank ever drops below zero. What happens if you try this for every possible s?

2Hint 2Explore hint

For each start s in 0..n−1, walk all n stations using modular indexing (i + s) % n, accumulating the net. If it never goes negative across all n hops, s works.

3Hint 3Explore hint

Two nested loops: outer over the candidate start, inner over the n stations of the loop. Return the first s that survives; if none do, return −1.

A · Core idea

The most direct reading of the problem: pick a start, drive the full circle, and see if the tank ever goes negative. Repeat for every possible start and return the first one that survives the loop.

Why this is the natural first attempt. The problem describes a physical simulation — pick up gas, pay to move on — so the literal solution is to run that simulation. With no insight required, you fix a start s, use (s + k) % n to wrap around the circle, and keep a running tank. The first s whose tank stays non-negative for all n hops is an answer.

Why the modular index matters. The route is circular, so after the last station you must return to station 0. Using (s + k) % n for k from 0 to n−1 visits every station exactly once in driving order starting from s, correctly modelling the wrap-around. Forgetting the modulo would simulate a straight line and miss the loop-closing cost.

Why we don't ship this. Each candidate start triggers a full n-station simulation, so the worst case is n × n = n² work. For n = 10⁵ that's up to 10¹⁰ operations — far too slow. Worse, it throws away information: when a simulation from s dies partway, the brute force restarts from s+1 from scratch, even though the failed stretch already told us those starts are hopeless. That wasted insight is exactly what the greedy reclaims.

B · Visual dry run

Interactive dry run

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

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

start=0

tank: 1−3 = −2 at station 0 → dies immediately

Statereject 0

Final result3

C · Code with teaching comments

Reference implementation previewpublic int canCompleteCircuit(int[] gas, int[] cost) { int n = gas.length; for (int start = 0; start < n; start++) { int tank = 0; boolean ok = true;Explore the full code

solution.javaJava

Brute Force — Simulate From Every Start — reference

4 teaching notes

1
public int canCompleteCircuit(int[] gas, int[] cost) {
2
    int n = gas.length;
3
    // Try every station as a candidate starting point.
4
    for (int start = 0; start < n; start++) {
5
        int tank = 0;
6
        boolean ok = true;
7
        for (int k = 0; k < n; k++) {
8
            // Modular index walks the circle in driving order, wrapping past the end
9
            // back to 0.
10
            int i = (start + k) % n;
11
            tank += gas[i] - cost[i];
12
            // Tank went negative — this start fails; abandon it and try the next.
13
            if (tank < 0) { ok = false; break; }
14
        }
15
        // Survived all n hops without going negative → valid start.
16
        if (ok) return start;
17
    }
18
    return -1;
19
}

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

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

When a run starting at s fails at some station j, the brute force learns something it immediately discards: no station between s and j could have been a valid start either. Noticing that you can skip straight to j + 1 instead of s + 1 is the seed of the linear greedy — the same 'the whole failing prefix is dead' idea behind Kadane's reset.

ComplexityO(n²) time, O(1) space — For each of n candidate starts we simulate up to n stations, so O(n²) time in the worst case; we only keep a running tank, so O(1) space.

E · Edge cases and pitfalls3Forgetting the % n wrap — simulates a line and never closes the loop.Explore edge cases

Pitfalls

Forgetting the % n wrap — simulates a line and never closes the loop.
Resetting only to start+1 after a failure instead of recognising the whole failed stretch is dead (the missed optimisation).
Shipping O(n²) when n = 10⁵ guarantees a time-limit exceeded.

03.2

Approach 2 of 2 · Optimal

Greedy — Total Check + Reset On Deficit (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'two separate questions: does a start exist, and where is it' — then justify the reset with the contradiction argument.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Split the problem. First: can ANY start work? That's a global question — compare total gas to total cost. If you're in deficit overall, no start can survive a full loop.

2Hint 2Explore hint

Now assume a start exists. Sweep left to right tracking a running tank of gas[i] − cost[i]. What does it mean if the tank goes negative somewhere between your current candidate start and station i?

3Hint 3Explore hint

If the tank dies at i, then NO station from the current start through i can be the answer — every one of them inherited an even worse running balance. So jump the candidate start to i + 1, reset the tank to 0, and keep sweeping. The surviving start is the answer.

A · Core idea

Separate the question into two cleaner ones. Existence: a full loop is possible if and only if sum(gas) >= sum(cost), because completing the circle means the total fuel gained must cover the total fuel spent — the tank starts and ends empty-or-positive over a closed loop. If the global total is in deficit, return -1 immediately. Location: assuming a start exists, sweep once with a running tank. Whenever tank drops below zero at station i, set start = i + 1 and reset tank = 0. The start left standing at the end is the unique answer.

Why total surplus guarantees a solution exists. Over one full loop the net change is sum(gas) − sum(cost). If that's negative, you burn more than you collect no matter where you begin, so -1. If it's ≥ 0, the closed-loop net is non-negative, which is exactly the condition under which some rotation of the sequence keeps every prefix non-negative — a classic result about circular sequences. So the global check isn't just necessary, it's sufficient.

Why a failing stretch disqualifies its entire span — the contradiction argument. Suppose we start at s and the running tank first goes negative when we arrive at station i (so the sum of nets over [s, i] is negative). Claim: no station t with s ≤ t ≤ i can be a valid start. Here's the contradiction: when we started at s, our tank was non-negative at every station before i — in particular it was ≥ 0 when we reached any intermediate t. If instead we began at t, we'd start that same sub-journey from a tank of 0, which is ≤ the tank we actually had arriving at t from s. So starting at t reaches i with an even lower balance than the run from s did — and that run already went negative. Therefore t fails too. Every candidate in [s, i] is dead, so the earliest station that could possibly work is i + 1. That is precisely why the reset jumps to i + 1 rather than crawling forward one step.

Why one pass with no re-wrap is enough. The reset argument means the surviving start is never disqualified by anything to its left. Combined with the existence guarantee from the total check, the stretch from start to the end of the array accumulates a non-negative running sum, and the leftover deficit before start is exactly cancelled by the surplus after it when the loop wraps. So we never need to simulate the wrap-around explicitly — the global surplus certifies the wrap closes. That collapses the O(n²) re-simulation into a single linear sweep.

Why this beats the brute force outright. The brute force rediscovers each failure from scratch; the greedy uses each failure to skip an entire doomed prefix, and replaces per-start re-simulation with one global comparison. Same answer, O(n²) → O(n), O(1) space throughout.

B · Visual dry run

Interactive dry run

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

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

Interactive diagram

Why the failed prefix is dead

i=0

Active call / nodeSupporting contextReturned stateNot active

If the tank dies at i starting from s, any start t in [s, i] begins from an even lower balance and dies too — so leap to i+1.

Final result3

C · Code with teaching comments

solution.javaJava

Greedy — Total Check + Reset On Deficit (Optimal) — optimal

6 teaching notes

1
public int canCompleteCircuit(int[] gas, int[] cost) {
2
    // total = global surplus (existence), tank = running balance since last reset
3
    // (location), start = current candidate.
4
    int total = 0, tank = 0, start = 0;
5
    for (int i = 0; i < gas.length; i++) {
6
        // Only the net per station matters — gain minus cost to move on.
7
        int diff = gas[i] - cost[i];
8
        // Accumulate the global surplus; its sign decides whether any start can work.
9
        total += diff;
10
        tank += diff;
11
        // Stretch from start..i is doomed — by the contradiction argument no station in
12
        // it can begin a successful loop.
13
        if (tank < 0) {
14
            // Jump past the entire failed prefix, not just one step.
15
            start = i + 1;
16
            tank = 0;
17
        }
18
    }
19
    // Surviving start is valid only if the global surplus is non-negative; otherwise no
20
    // start completes the loop.
21
    return total >= 0 ? start : -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

The unlock is realising these are two independent questions wearing one disguise: whether a start exists is global (sum of nets), and which start works is local (where does the running balance survive). The reset is the same move as Kadane's 'a negative running prefix can only hurt, so drop it' — here a negative running tank means the whole prefix since the last reset is unsalvageable, so you leap past all of it at once.

ComplexityO(n) time, O(1) space — One pass to compute the totals (or folded into the same loop) plus one sweep that resets in place — each station is touched a constant number of times, giving O(n) time and O(1) space (just two running integers).

E · Edge cases and pitfalls6gas = [2, 3, 4], cost = [3, 4, 3] — total = (−1) + (−1) + 1 = −1 < 0, so regardless of the sweep's surviving start, the final check returns −1.Explore edge cases

Edge cases handled

gas = [2, 3, 4], cost = [3, 4, 3]total = (−1) + (−1) + 1 = −1 < 0, so regardless of the sweep's surviving start, the final check returns −1.
gas = [5], cost = [4]Single station: diff = 1, total = 1 ≥ 0, tank never negative → start stays 0, returns 0.
gas = [3, 1, 1], cost = [1, 2, 2]total = 2 + (−1) + (−1) = 0 ≥ 0; tank dips at i=2 (resets start=2 only if it goes negative) — surviving start completes the loop because surplus is exactly zero.

Pitfalls

Returning start without the total >= 0 guard — gives a wrong index when no solution exists.
Resetting start but forgetting to also zero the tank — carries a phantom deficit into the next candidate.
Re-simulating the wrap-around explicitly — unnecessary once the total surplus certifies the loop closes.

Practice

Try the solution yourself

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

Editable code previewpublic int canCompleteCircuit(int[] gas, int[] cost) { int total = 0, tank = 0, start = 0; for (int i = 0; i < gas.length; i++) { int diff = gas[i] - cost[i]; total += diff;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.

Returning start without the feasibility guard

The sweep always leaves some surviving start, but it's only valid when the global surplus is non-negative. Skipping the total check returns a bogus index on infeasible inputs.

Explore the code comparison

Don't write this

int tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
    tank += gas[i] - cost[i];
    if (tank < 0) { start = i + 1; tank = 0; }
}
return start; // wrong: no existence check

Write this instead

int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
    int diff = gas[i] - cost[i];
    total += diff; tank += diff;
    if (tank < 0) { start = i + 1; tank = 0; }
}
return total >= 0 ? start : -1;

Forgetting to reset the tank on a deficit

Advancing start but keeping the negative tank drags the old deficit into the new candidate's balance, corrupting every later comparison.

Explore the code comparison

Don't write this

if tank < 0:
    start = i + 1
    # tank not reset — carries the deficit forward

Write this instead

if tank < 0:
    start = i + 1
    tank = 0

Crawling forward one station after a failure

The contradiction argument proves the entire stretch [start, i] is dead, so moving start to i+1 is correct and O(n). Moving to start+1 and re-checking reintroduces the O(n²) brute force.

Explore the code comparison

Don't write this

if (tank < 0) {
    start = start + 1; // re-tests doomed stations
    i = start - 1;     // restart sweep — quadratic
    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 circular feasibility — total check + reset-on-deficit

Code pattern to memorize

if sum(gas) < sum(cost): return -1
start = 0; tank = 0
for i in range(n):
    tank += gas[i] - cost[i]
    if tank < 0:        # stretch [start..i] is doomed
        start = i + 1
        tank = 0
return start

Rules to remember

1First settle existence: a solution exists iff sum(gas) >= sum(cost). No total surplus → return -1.
2Track a running `tank` of gas[i] - cost[i]. The instant it goes negative, every station from the current start through i is disqualified as a start.
3On a deficit, reset start = i + 1 and tank = 0 — never re-test the stations you just abandoned.
4You make exactly one pass; you never wrap around and re-simulate, because the total check already guarantees the surviving start completes the loop.
5Use the net array diff[i] = gas[i] - cost[i] mentally — the question is purely about a circular running sum staying non-negative.
6The answer is unique when it exists, so the first surviving start is the answer — no tie-breaking needed.

Use this pattern when

Circular / wrap-around route where you accumulate then spend a resource
You need a feasible *starting point*, not the full schedule
A running balance must stay non-negative across a loop
Total surplus guarantees a solution and you want to locate it in one sweep

Choose another pattern when

Resource can be carried over multiple loops → it's not a single-circuit feasibility question
You must return *all* valid starts, not one → the uniqueness shortcut breaks
Costs depend on the order you visit (not fixed per edge) → model as a graph, not a linear sweep
Negative-only or fractional refuel rules → simulate or use a different model

Interview takeaway

Gas Station is the canonical 'circular running-sum' greedy: one global check decides existence, and a single reset-on-deficit sweep locates the unique start. The reset trick — 'the whole failing prefix is disqualified, jump past it' — is the same move you use in Maximum Subarray (Kadane) and Jump Game's frontier reset.

Continue

Transfer the pattern to another problem

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

Transferable patternCanonical circular running-sum greedy: a single global sum decides existence, and a reset-on-deficit sweep locates the unique start in one pass. Recognise it for wrap-around feasibility where a balance must stay non-negative; it shares its reset spirit with Kadane's Maximum Subarray and Jump Game's frontier.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Subarray
Coming soon
Kadane's reset is the same idea — drop a running prefix the instant it turns negative.
Jump Game
Linear feasibility with a running frontier rather than a running tank — same one-pass greedy flavour.
Minimum Number of Refueling Stops
Coming soon
Fuel feasibility where you choose when to refuel — greedy with a max-heap of passed stations.
Gas Station (return all starts)
If uniqueness were dropped, you'd lose the early-return shortcut and need to collect every surviving rotation.

Same pattern

←

Jump Game II

Continue · Next problem

Hand of Straights

mediumGreedyLC #134Frequently asked

Gas Station

LCPractice

Greedy Algorithms · 3 of 23 · 10 min

There are n gas stations along a circular route, where the amount of gas at the i-th station is gas[i].

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

If there exists a solution, it is guaranteed to be unique.

In plain English

Examples

Example 1

Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Note: Start at index 3: tank = 4. To 4: +5−1 = 8. To 0: +1−2 = 7. To 1: +2−3 = 6. To 2: +3−4 = 5. To 3: arrive with 5 ≥ 0 — full loop done.

Example 2

Input: gas = [2, 3, 4], cost = [3, 4, 3]
Output: -1
Note: Total gas 9 < total cost 10, so no starting station can complete the circuit.

Example 3

Input: gas = [5, 1, 2, 3, 4], cost = [4, 4, 1, 5, 1]
Output: 4
Note: Total gas 15 ≥ total cost 15, so a unique start exists; the sweep lands on index 4.

Constraints

n == gas.length == cost.length
1 ≤ n ≤ 10⁵
0 ≤ gas[i], cost[i] ≤ 10⁴
The answer is guaranteed to be unique if it exists

Clarifying questions4First question: Is the route truly circular — does the last station wrap back to the first?Explore questions

Q1.Is the route truly circular — does the last station wrap back to the first?
Yes. From station n−1 you pay cost[n−1] to return to station 0. That wrap-around is why a single linear scan needs justification.
Q2.Can the answer be ambiguous — multiple valid starts?
No, the problem guarantees a unique answer when one exists. That uniqueness is what lets us return the first surviving start without checking the rest.
Q3.What if total gas exactly equals total cost?
Then a solution exists (surplus is zero, which is allowed — the tank may touch but never drop below zero across the full loop).
Q4.Are gas and cost always non-negative?
Yes, both are in [0, 10⁴], so each net diff is in [−10⁴, 10⁴]. No tricks with negative fuel pickups.

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

Where candidates slip

How to stand out

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)`	Open with this to show you understand the mechanics of the circuit, then call out the O(n²) cost as the reason to look deeper.	Read
2	Greedy — Total Check + Reset On Deficit (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'two separate questions: does a start exist, and where is it' — then justify the reset with the contradiction argument.	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)

Open with this to show you understand the mechanics of the circuit, then call out the O(n²) cost as the reason to look deeper.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you fix a starting station s, you can just drive: add gas[i] − cost[i] as you go and watch whether the tank ever drops below zero. What happens if you try this for every possible s?

2Hint 2Explore hint

For each start s in 0..n−1, walk all n stations using modular indexing (i + s) % n, accumulating the net. If it never goes negative across all n hops, s works.

3Hint 3Explore hint

Two nested loops: outer over the candidate start, inner over the n stations of the loop. Return the first s that survives; if none do, return −1.

A · Core idea

The most direct reading of the problem: pick a start, drive the full circle, and see if the tank ever goes negative. Repeat for every possible start and return the first one that survives the loop.

B · Visual dry run

Interactive dry run

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

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

start=0

tank: 1−3 = −2 at station 0 → dies immediately

Statereject 0

Final result3

C · Code with teaching comments

solution.javaJava

Brute Force — Simulate From Every Start — reference

4 teaching notes

1
public int canCompleteCircuit(int[] gas, int[] cost) {
2
    int n = gas.length;
3
    // Try every station as a candidate starting point.
4
    for (int start = 0; start < n; start++) {
5
        int tank = 0;
6
        boolean ok = true;
7
        for (int k = 0; k < n; k++) {
8
            // Modular index walks the circle in driving order, wrapping past the end
9
            // back to 0.
10
            int i = (start + k) % n;
11
            tank += gas[i] - cost[i];
12
            // Tank went negative — this start fails; abandon it and try the next.
13
            if (tank < 0) { ok = false; break; }
14
        }
15
        // Survived all n hops without going negative → valid start.
16
        if (ok) return start;
17
    }
18
    return -1;
19
}

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

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

ComplexityO(n²) time, O(1) space — For each of n candidate starts we simulate up to n stations, so O(n²) time in the worst case; we only keep a running tank, so O(1) space.

E · Edge cases and pitfalls3Forgetting the % n wrap — simulates a line and never closes the loop.Explore edge cases

Pitfalls

Forgetting the % n wrap — simulates a line and never closes the loop.
Resetting only to start+1 after a failure instead of recognising the whole failed stretch is dead (the missed optimisation).
Shipping O(n²) when n = 10⁵ guarantees a time-limit exceeded.

03.2

Approach 2 of 2 · Optimal

Greedy — Total Check + Reset On Deficit (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'two separate questions: does a start exist, and where is it' — then justify the reset with the contradiction argument.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Split the problem. First: can ANY start work? That's a global question — compare total gas to total cost. If you're in deficit overall, no start can survive a full loop.

2Hint 2Explore hint

Now assume a start exists. Sweep left to right tracking a running tank of gas[i] − cost[i]. What does it mean if the tank goes negative somewhere between your current candidate start and station i?

3Hint 3Explore hint

A · Core idea

B · Visual dry run

Interactive dry run

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

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

Interactive diagram

Why the failed prefix is dead

i=0

Active call / nodeSupporting contextReturned stateNot active

If the tank dies at i starting from s, any start t in [s, i] begins from an even lower balance and dies too — so leap to i+1.

Final result3

C · Code with teaching comments

solution.javaJava

Greedy — Total Check + Reset On Deficit (Optimal) — optimal

6 teaching notes

1
public int canCompleteCircuit(int[] gas, int[] cost) {
2
    // total = global surplus (existence), tank = running balance since last reset
3
    // (location), start = current candidate.
4
    int total = 0, tank = 0, start = 0;
5
    for (int i = 0; i < gas.length; i++) {
6
        // Only the net per station matters — gain minus cost to move on.
7
        int diff = gas[i] - cost[i];
8
        // Accumulate the global surplus; its sign decides whether any start can work.
9
        total += diff;
10
        tank += diff;
11
        // Stretch from start..i is doomed — by the contradiction argument no station in
12
        // it can begin a successful loop.
13
        if (tank < 0) {
14
            // Jump past the entire failed prefix, not just one step.
15
            start = i + 1;
16
            tank = 0;
17
        }
18
    }
19
    // Surviving start is valid only if the global surplus is non-negative; otherwise no
20
    // start completes the loop.
21
    return total >= 0 ? start : -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

Edge cases handled

gas = [2, 3, 4], cost = [3, 4, 3]total = (−1) + (−1) + 1 = −1 < 0, so regardless of the sweep's surviving start, the final check returns −1.
gas = [5], cost = [4]Single station: diff = 1, total = 1 ≥ 0, tank never negative → start stays 0, returns 0.
gas = [3, 1, 1], cost = [1, 2, 2]total = 2 + (−1) + (−1) = 0 ≥ 0; tank dips at i=2 (resets start=2 only if it goes negative) — surviving start completes the loop because surplus is exactly zero.

Pitfalls

Returning start without the total >= 0 guard — gives a wrong index when no solution exists.
Resetting start but forgetting to also zero the tank — carries a phantom deficit into the next candidate.
Re-simulating the wrap-around explicitly — unnecessary once the total surplus certifies the loop closes.

Practice

Try the solution yourself

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

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.

Returning start without the feasibility guard

The sweep always leaves some surviving start, but it's only valid when the global surplus is non-negative. Skipping the total check returns a bogus index on infeasible inputs.

Explore the code comparison

Don't write this

int tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
    tank += gas[i] - cost[i];
    if (tank < 0) { start = i + 1; tank = 0; }
}
return start; // wrong: no existence check

Write this instead

int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
    int diff = gas[i] - cost[i];
    total += diff; tank += diff;
    if (tank < 0) { start = i + 1; tank = 0; }
}
return total >= 0 ? start : -1;

Forgetting to reset the tank on a deficit

Advancing start but keeping the negative tank drags the old deficit into the new candidate's balance, corrupting every later comparison.

Explore the code comparison

Don't write this

if tank < 0:
    start = i + 1
    # tank not reset — carries the deficit forward

Write this instead

if tank < 0:
    start = i + 1
    tank = 0

Crawling forward one station after a failure

The contradiction argument proves the entire stretch [start, i] is dead, so moving start to i+1 is correct and O(n). Moving to start+1 and re-checking reintroduces the O(n²) brute force.

Explore the code comparison

Don't write this

if (tank < 0) {
    start = start + 1; // re-tests doomed stations
    i = start - 1;     // restart sweep — quadratic
    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 circular feasibility — total check + reset-on-deficit

Code pattern to memorize

if sum(gas) < sum(cost): return -1
start = 0; tank = 0
for i in range(n):
    tank += gas[i] - cost[i]
    if tank < 0:        # stretch [start..i] is doomed
        start = i + 1
        tank = 0
return start

Rules to remember

1First settle existence: a solution exists iff sum(gas) >= sum(cost). No total surplus → return -1.
2Track a running `tank` of gas[i] - cost[i]. The instant it goes negative, every station from the current start through i is disqualified as a start.
3On a deficit, reset start = i + 1 and tank = 0 — never re-test the stations you just abandoned.
4You make exactly one pass; you never wrap around and re-simulate, because the total check already guarantees the surviving start completes the loop.
5Use the net array diff[i] = gas[i] - cost[i] mentally — the question is purely about a circular running sum staying non-negative.
6The answer is unique when it exists, so the first surviving start is the answer — no tie-breaking needed.

Use this pattern when

Circular / wrap-around route where you accumulate then spend a resource
You need a feasible *starting point*, not the full schedule
A running balance must stay non-negative across a loop
Total surplus guarantees a solution and you want to locate it in one sweep

Choose another pattern when

Resource can be carried over multiple loops → it's not a single-circuit feasibility question
You must return *all* valid starts, not one → the uniqueness shortcut breaks
Costs depend on the order you visit (not fixed per edge) → model as a graph, not a linear sweep
Negative-only or fractional refuel rules → simulate or use a different model

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

Maximum Subarray
Coming soon
Kadane's reset is the same idea — drop a running prefix the instant it turns negative.
Jump Game
Linear feasibility with a running frontier rather than a running tank — same one-pass greedy flavour.
Minimum Number of Refueling Stops
Coming soon
Fuel feasibility where you choose when to refuel — greedy with a max-heap of passed stations.
Gas Station (return all starts)
If uniqueness were dropped, you'd lose the early-return shortcut and need to collect every surviving rotation.

Same pattern

←

Jump Game II

Continue · Next problem

Hand of Straights