Gas Station
Problem
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 without running out of gas; otherwise, return -1.
- gas.length == cost.length
- 1 ≤ gas.length ≤ 10⁵
- 0 ≤ gas[i], cost[i] ≤ 10⁴
Example
gas = [1,2,3,4,5], cost = [3,4,5,1,2]3The total gas is 15 and total cost is 15, so a solution exists. Starting at station 3, the car accumulates gas and cost as follows: at station 3, gas=4, cost=1, net=+3; at station 4, gas=5, cost=2, net=+3; at station 0, gas=1, cost=3, net=+1; at station 1, gas=2, cost=4, net=-1; at station 2, gas=3, cost=5, net=-3. The cumulative net never drops below zero starting from station 3, so station 3 is the valid start.
Approach
Straightforward Solution
A brute-force approach tries starting from each station and simulates the entire trip, which is O(n^2) and too slow for large inputs.
Core Observation
If the total amount of gas is less than the total cost, it is impossible to complete the circuit regardless of the starting point. Conversely, if total gas is at least total cost, there must be a unique starting station from which the circuit can be completed.
Path to Optimal
The key insight is to track the cumulative net gas (gas[i] - cost[i]) as we iterate through stations. Whenever the cumulative net drops below zero, it means the current start station cannot reach station i+1. Therefore, the next station (i+1) becomes the new candidate start. This greedy reset ensures that the final candidate start is the unique valid station if total gas >= total cost.
Optimal Approach
First, check if total gas is less than total cost; if yes, return -1 immediately. Otherwise, iterate through the stations, accumulating net gas. When the net drops below zero, reset the net to zero and update the start station to the next index. After one pass, return the start station index. This approach runs in O(n) time and O(1) space.
Time
O(n)
The algorithm makes a single pass through the gas stations, performing constant time operations per station.
Space
O(1)
Only a few integer variables are used to track totals and indices, regardless of input size.
Pattern Spotlight
Greedy Algorithms (Single Pass Feasibility and Reset)
When a cumulative metric drops below zero, the current candidate start cannot lead to a valid solution, so reset the candidate start to the next position and reset the cumulative metric, ensuring a single pass finds the unique valid start if it exists.
Solution
| 1 | class Solution:
|
| 2 | def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
|
| 3 | if sum(gas) < sum(cost):
|
| 4 | return -1
|
| 5 |
|
| 6 | total = 0
|
| 7 | start_station = 0
|
| 8 | for i in range(len(gas)):
|
| 9 | total += (gas[i] - cost[i])
|
| 10 |
|
| 11 | if total < 0:
|
| 12 | total = 0
|
| 13 | start_station = i + 1
|
| 14 |
|
| 15 | return start_station |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public int canCompleteCircuit(int[] gas, int[] cost) { |
| 5 | int sumGas = 0, sumCost = 0; |
| 6 | for (int g : gas) sumGas += g; |
| 7 | for (int c : cost) sumCost += c; |
| 8 | if (sumGas < sumCost) return -1; |
| 9 | |
| 10 | int total = 0; |
| 11 | int startStation = 0; |
| 12 | for (int i = 0; i < gas.length; i++) { |
| 13 | total += gas[i] - cost[i]; |
| 14 | if (total < 0) { |
| 15 | total = 0; |
| 16 | startStation = i + 1; |
| 17 | } |
| 18 | } |
| 19 | return startStation; |
| 20 | } |
| 21 | } |
| 1 | #include <vector> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { |
| 8 | int sumGas = 0, sumCost = 0; |
| 9 | for (int g : gas) sumGas += g; |
| 10 | for (int c : cost) sumCost += c; |
| 11 | if (sumGas < sumCost) return -1; |
| 12 | |
| 13 | int total = 0; |
| 14 | int startStation = 0; |
| 15 | for (int i = 0; i < (int)gas.size(); i++) { |
| 16 | total += gas[i] - cost[i]; |
| 17 | if (total < 0) { |
| 18 | total = 0; |
| 19 | startStation = i + 1; |
| 20 | } |
| 21 | } |
| 22 | return startStation; |
| 23 | } |
| 24 | }; |
| 1 | var canCompleteCircuit = function(gas, cost) { |
| 2 | let sumGas = 0, sumCost = 0; |
| 3 | for (let g of gas) sumGas += g; |
| 4 | for (let c of cost) sumCost += c; |
| 5 | if (sumGas < sumCost) return -1; |
| 6 | |
| 7 | let total = 0; |
| 8 | let startStation = 0; |
| 9 | for (let i = 0; i < gas.length; i++) { |
| 10 | total += gas[i] - cost[i]; |
| 11 | if (total < 0) { |
| 12 | total = 0; |
| 13 | startStation = i + 1; |
| 14 | } |
| 15 | } |
| 16 | return startStation; |
| 17 | }; |
Step-by-Step Solution
Verify Total Gas Sufficiency to Guarantee a Solution
| 3 | if sum(gas) < sum(cost):
|
| 4 | return -1
|
Objective
To quickly determine if completing the circuit is impossible by comparing total gas and total cost.
Key Insight
If the sum of all gas is less than the sum of all costs, no starting point can complete the circuit. This early check prevents unnecessary computation and immediately returns -1 for impossible cases.
Interview Quick-Check
Core Logic
The total gas must be at least the total cost for any solution to exist.
Common Pitfalls & Bugs
Failing to perform this check can lead to incorrect results or inefficient attempts to find a start station when none exists.
Iterate Stations to Identify Valid Start via Cumulative Net Reset
| 6 | total = 0
|
| 7 | start_station = 0
|
| 8 | for i in range(len(gas)):
|
| 9 | total += (gas[i] - cost[i])
|
| 11 | if total < 0:
|
| 12 | total = 0
|
| 13 | start_station = i + 1
|
Objective
To find the unique valid start station by tracking cumulative net gas and resetting when it drops below zero.
Key Insight
Accumulating the net gas (gas[i] - cost[i]) simulates the fuel balance as the car moves. When this balance becomes negative, it proves the current start cannot reach the next station. Resetting the cumulative net and moving the start to the next station leverages the greedy insight that no station between the old start and current index can be valid, enabling a single pass solution.
Interview Quick-Check
Core Logic
Resetting the cumulative net and start index when net drops below zero ensures the algorithm skips invalid start points efficiently.
State & Boundaries
The loop covers all stations exactly once, guaranteeing O(n) time.
Common Pitfalls & Bugs
Not resetting the cumulative net or start index correctly leads to incorrect start station identification.
Return the Identified Valid Start Station
| 15 | return start_station |
Objective
To output the unique valid start station index after completing the iteration.
Key Insight
After the single pass, the start_station variable holds the index from which the car can complete the circuit. Returning this value finalizes the solution.
Interview Quick-Check
Core Logic
Returning the start_station after the loop completes provides the unique valid start guaranteed by the problem constraints.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
if sum(gas) < sum(cost):Check if total gas is less than total cost.
This line implements the fundamental feasibility check: if total gas is insufficient to cover total cost, no solution exists, allowing early termination.
if total < 0:Check if cumulative net gas has dropped below zero.
A negative cumulative net indicates the current start station cannot reach station i+1, triggering a reset.
start_station = i + 1Update start station to the next index after failure.
Moving the start to i+1 leverages the greedy insight that no station between the old start and i can be valid, ensuring correctness and efficiency.
return -1Return -1 immediately if circuit completion is impossible.
Returning -1 here prevents unnecessary computation and correctly signals that no valid start station exists.
total += (gas[i] - cost[i])Update cumulative net gas by adding gas[i] minus cost[i].
This calculation simulates the fuel gained and spent at station i, tracking the car's fuel balance.
total = 0Reset cumulative net gas to zero after failure.
Resetting net to zero discards the invalid partial journey and prepares to test a new start station.
return start_stationReturn the identified valid start station index.
Returning start_station finalizes the solution, as it holds the unique valid start guaranteed by the problem.
total = 0Initialize cumulative net gas to zero.
This variable tracks the net gas balance as the car moves through stations, essential for detecting when the current start fails.
start_station = 0Initialize start station index to zero.
This variable holds the candidate start station, updated whenever the cumulative net drops below zero.
for i in range(len(gas)):Iterate over each gas station index.
This loop processes stations in order, simulating the car's journey around the circuit.
Test Your Understanding
Why can the algorithm reset the start station to i+1 when the cumulative net gas drops below zero at station i?
Because if the cumulative net gas is negative at station i, it means starting from the current candidate start cannot reach station i+1; any station between the current start and i would also fail, so the next station i+1 is the earliest possible valid start.
Related Problems
Greedy pattern
Don't just read it. Drill it.
Reconstruct Gas Station from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Gas Station drill