134. Gas Station

At a Glance

Topic: greedy
Pattern: Greedy (single pass with restart)
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Bloomberg, Apple
Frequency: Medium
LeetCode: 134

Circular route: gas[index] fuel gained, cost[index] to reach next station. Start with empty tank at some station start. Return any start where you can complete a full circuit, or -1 if impossible. Input: gas, cost equal length. Output: start index or -1.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

“Circular tour” / circuit
Net fuel delta[index] = gas[index] - cost[index]
If total delta < 0, impossible; else a unique greedy start exists

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — try each start — O(n²) time.
Greedy — accumulate tank; restart candidate start when tank drops below zero — O(n) time / O(1) space. <- pick this in interview.

Optimal Solution

Go

package main

func canCompleteCircuit(gas []int, cost []int) int {
	totalBalance := 0
	currentTank := 0
	startIndex := 0
	for index := range gas {
		delta := gas[index] - cost[index]
		totalBalance += delta
		currentTank += delta
		if currentTank < 0 {
			startIndex = index + 1
			currentTank = 0
		}
	}
	if totalBalance < 0 {
		return -1
	}
	return startIndex
}

JavaScript

function canCompleteCircuit(gas, cost) {
	let totalBalance = 0;
	let currentTank = 0;
	let startIndex = 0;
	for (let index = 0; index < gas.length; index++) {
		const delta = gas[index] - cost[index];
		totalBalance += delta;
		currentTank += delta;
		if (currentTank < 0) {
			startIndex = index + 1;
			currentTank = 0;
		}
	}
	return totalBalance < 0 ? -1 : startIndex;
}

Walkthrough

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

Deltas: -2,-2,-2,3,3, total 0. Tank goes negative until restart after failing prefix; final start works.

Invariant: if total gas ≥ total cost, the greedy restart lands on a valid unique starting station.

Edge Cases

Single station: need gas[0] >= cost[0]
Total surplus negative → -1

Pitfalls

Using modulo indexing inside inner loops (O(n²))
Integer overflow on totals (use 64-bit if needed)

Variants

Multiple vehicles → different problem.

Mind-Map Tags

#greedy #circular-array #tank-balance #medium