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.

Recognition Cues

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

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;
}