How do you solve Gas Station?

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.

Gas Station

Q: What is the time complexity of Gas Station?

O(n). The algorithm makes a single pass through the gas stations, performing constant time operations per station.

Q: What pattern does Gas Station use?

The Pattern: Greedy Algorithms (Single Pass Feasibility and Reset) The Heuristic: 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.

Medium Greedy Algorithms

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

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

Output: 3

The 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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

First, check if total gas is less than total cost; if yes, return -1 immediately. Otherwise, iterate through the stations, accumulating net gas…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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

Python

1class Solution:
  def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
      if sum(gas) < sum(cost):
          return -1
5
      total = 0
      start_station = 0
      for i in range(len(gas)):
          total += (gas[i] - cost[i])
10
          if total < 0:
              total = 0
              start_station = i + 1
      
      return start_station

Step-by-Step Solution

Verify Total Gas Sufficiency to Guarantee a Solution

3if 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

To find the unique valid start station by tracking cumulative net gas and resetting when it drops below zero.

Return the Identified Valid Start Station

To output the unique valid start station index after completing the iteration.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 3 Critical

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.

Line 11 Critical

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.

Line 13 Critical

start_station = i + 1

Update 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.

Full line-by-line criticality + rationale for all 10 lines available on Pro.

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?

See the answer with Pro.

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

or drill a free problem

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`