Skip to content

Volume ITechnology

4.26.4 — Gas Station ​

LeetCode 134 · Medium

The problem ​

Stations are arranged in a circle. At station i you gain gas[i] fuel, and driving to station i+1 costs cost[i]. Starting with an empty tank, return the index you must start from to complete the loop, or -1 if it is impossible. The answer is guaranteed unique if it exists.

Restating the Problem: You have a car that starts with zero fuel. You must pick a starting station on a circular route. At each station, you pump gas[i] into your tank, and driving to the next station consumes cost[i]. You must complete the circle without your fuel ever dropping below 0.

  • Constraints to note: The arrays gas and cost have the same length N, which can be up to 10^5. This implies we need an O(N) algorithm.
  • Edge cases: The net gas might be exactly zero at the end; this is a valid trip, provided you don't drop below zero midway.
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]      →  3

gas  = [2,3,4]
cost = [3,4,3]          →  -1

The pattern ​

Work with the net gain at each station, gas[i] - cost[i]. Now the question is: from which starting point can you go all the way round without the running total ever dropping below zero?

Two facts do all the work, and both need proving.

Fact 1 — a solution exists exactly when the total net gain is non-negative.

If the total is negative, you burn more fuel than you collect over a full loop, so no start can work. If it is non-negative, a valid start is guaranteed to exist. The first direction is obvious; the second falls out of Fact 2.

Fact 2 — if you run out of fuel travelling from start to i, then no station between them works either.

This fact is what makes the algorithm one pass, so here is the proof. Suppose you start at start and fail on the way to station i. Take any station j strictly between them. You arrived at j with a non-negative tank, otherwise you would have failed earlier than i. Starting at j instead means arriving at each later station with less fuel than before. So you fail at i too, or sooner.

So the whole stretch from start to i can be skipped in one step. Every index is tested at most once, and the scan is linear.

The solution ​

python
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):  # (1)
            return -1                        # not enough fuel in total

        start = 0  # (2)
        tank = 0  # (3)

        for i in range(len(gas)):  # (4)
            tank += gas[i] - cost[i]  # (5)

            if tank < 0:                     # (6) cannot reach station i+1
                start = i + 1                # (7) skip the whole stretch
                tank = 0                     # (8) start fresh from there

        return start  # (9)
ts
function canCompleteCircuit(gas: number[], cost: number[]): number {
  const total = gas.reduce((a, b) => a + b, 0) - cost.reduce((a, b) => a + b, 0);  // (1)
  if (total < 0) return -1;

  let start = 0, tank = 0;  // (2)

  for (let i = 0; i < gas.length; i++) {  // (4)
    tank += gas[i] - cost[i];  // (5)
    if (tank < 0) {  // (6)
      start = i + 1;  // (7)
      tank = 0;  // (8)
    }
  }

  return start;  // (9)
}

Line by line ​

(1) If there is less fuel in total than the trip needs, no start can work. Return −1. If there is enough in total, the problem promises exactly one start works, and the rest of the code finds it.

(2) The candidate starting station.

(3) Fuel in the tank since that start.

(4) Drive through every station once.

(5) Fill up at station i, then pay the fuel to reach station i + 1.

(6) The tank went negative, so we cannot reach station i + 1 from start.

(7) Then no station from start to i can be the answer either, so the next candidate is i + 1. Here is why. Every station between start and i was reached with a tank of zero or more. Starting at one of them means arriving there with an empty tank instead, which is no better. So starting there would also run dry before i + 1.

(8) The new candidate starts with an empty tank.

(9) The last candidate standing is the answer. Line (1) already confirmed there is enough fuel overall, so the trip from this start never runs dry.

No wraparound is needed anywhere. That looks wrong for a circular problem, and it is not.

Once the total check has passed, a valid start exists. The scan finds the last position from which the tank never goes negative through to the end of the array. Because the overall total is non-negative, the fuel accumulated across the skipped prefix is enough to cover the wrap. So the remaining stretch plus the wrap succeeds, and there is nothing to simulate.

Code Walkthrough:

  • Initial Viability Check (sum(gas) < sum(cost)): We immediately rule out impossible cases. If the total gas available across all stations is less than the total cost to travel, no starting point can possibly work.
  • Iteration: We loop through each station i. We track our current tank level and our proposed start index.
  • Accumulate Fuel: At each step, we add the net gain (gas[i] - cost[i]) to our tank.
  • Handling Failure (tank < 0): If the tank drops below zero, it means we cannot reach station i+1 from our current start. Due to Fact 2, we know no station between start and i could have worked either. So, we make i+1 our new proposed start and reset tank to 0.
  • Return: If we finish the loop, start holds the correct answer (guaranteed by the initial sum check).

tank resets to 0 on failure, because you are now considering a fresh journey beginning at i + 1.

The uniqueness guarantee is what lets the code return the first candidate it finds without checking whether an earlier one also works.

Trace ​

gas = [1,2,3,4,5], cost = [3,4,5,1,2]. Net: [-2,-2,-2,3,3]. Total is 0, so a solution exists.

inettankaction
0−2−2negative → start = 1, tank 0
1−2−2negative → start = 2, tank 0
2−2−2negative → start = 3, tank 0
3+33fine
4+36fine

Answer 3 ✓. Starting at 3: tank 3, then 6, then wrapping through the three negative stations 6 − 2 − 2 − 2 = 0, arriving back exactly empty.

Edge cases ​

  • Not enough fuel in total. Line (1) returns −1.
  • One station with enough fuel to return to itself. The answer is 0.
  • The tank runs dry at the last station. That cannot happen when line (1) passed, because the total over the whole circle is zero or more.

Complexity ​

O(n) time, O(1) space.

  • Time Complexity: O(n). We calculate the total sum once, and then iterate through the array once. At each station, we do a constant amount of math.
  • Space Complexity: O(1). We only track two variables, start and tank, using no extra data structures.

The brute force tries every start and simulates a full loop — O(n^2). Fact 2 is what removes the outer loop.

Where this goes next ​

  • Maximum Subarray — the same "reset when the running total goes negative" rule, and the same exchange argument behind it. 4.26.1.
  • Maximum Sum Circular Subarray — circular again, handled by splitting into wrapping and non-wrapping cases.
  • Candy — another greedy that needs two passes and a proof.

The transferable idea: when a failed attempt rules out a whole range of alternatives, the outer loop disappears. That is the same reasoning as the run-start guard in 4.4.9 and the discard proofs in 4.5.

What the interviewer will push on ​

"Why does a non-negative total guarantee a solution?" Because of Fact 2 — the scan always terminates at a start whose remaining stretch works, and the total guarantees the wrap is covered.

"Why can you skip the whole stretch after a failure?" The proof above: any intermediate station is reached with a non-negative tank, so starting there gives you no more fuel at any later point.

"Why is there no wraparound in the code?" The total check has already accounted for it.

"What if the answer were not unique?" The code returns the first valid start it finds, which is still a correct answer. If you needed all of them, you would collect every candidate and verify each — O(n^2) worst case.

"What is the brute force?" O(n^2), and Fact 2 is what kills the outer loop.

One thing to volunteer: give Fact 2 with its proof before writing the code. This problem is short but almost impossible to justify without it, and an unjustified greedy is a guess.

Next: 4.26.5 Hand of Straights — a greedy where the only decision is which card to start from.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet