Skip to main content
Talentd

Gas Station - Solution & Explanation

MediumArrayGreedy19 min readAsked at: Amazon, Microsoft, Apple +26
Practice this problem

Problem Statement

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

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, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

 

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

 

Constraints:

  • n == gas.length == cost.length
  • 1 <= n <= 105
  • 0 <= gas[i], cost[i] <= 104

Approach Overview

Problem Overview: You are given two integer arrays gas and cost. gas[i] is the fuel available at station i, and cost[i] is the fuel needed to travel from station i to i+1. The stations form a circle. Your task is to find the starting station index that allows you to complete the entire loop without running out of gas, or return -1 if it is impossible.

Approach 1: Brute Force Simulation (O(n²) time, O(1) space)

Try every station as the starting point and simulate the full trip around the circle. For each candidate start i, maintain a running tank value: add gas[j], subtract cost[j], and move to the next station using modulo to wrap around the array. If the tank ever becomes negative, that starting point fails. If you complete n steps successfully, that index is the answer. This direct simulation uses only constant extra memory but requires up to n attempts with up to n steps each, resulting in O(n²) time. It’s useful for understanding the mechanics of the circular route but does not scale well for large inputs.

Approach 2: Greedy Single Pass (O(n) time, O(1) space)

The key observation: if the total gas across all stations is less than the total travel cost, completing the circuit is impossible. Otherwise, a valid start must exist. Traverse the array once while maintaining two values: totalTank (overall gas minus cost) and currTank (fuel since the current candidate start). When currTank becomes negative at station i, any station between the current start and i cannot be a valid start. Reset the candidate start to i + 1 and reset currTank to zero. Continue scanning until the end of the array. If totalTank >= 0, the final candidate start index is guaranteed to complete the circuit. This greedy reasoning avoids rechecking failed segments and runs in linear time.

This technique works because once a deficit occurs, the accumulated shortage cannot be compensated by any station inside the failed segment. Skipping directly to the next index eliminates redundant checks. The algorithm operates entirely on the input arrays, making it both time and space efficient. The problem is a classic example of reasoning with cumulative balance in array traversal and applying a greedy decision rule.

Recommended for interviews: The greedy O(n) solution is the expected answer. Interviewers want to see the insight that eliminates unnecessary starting positions after a deficit. Mentioning the brute force simulation first shows you understand the problem mechanics, but deriving the greedy reset rule demonstrates stronger algorithmic reasoning.

Approach 1: Greedy Approach

This approach leverages the greedy paradigm. The main idea is to iterate over the stations while keeping track of the total gas and total cost. Additionally, we maintain a running sum (which is the cumulative balance of gas at each station) and a start index. If the running sum ever becomes negative, it implies that the current segment of the journey is infeasible. Thus, we reset the running sum and choose the next station as the candidate for the starting point. Finally, if the total gas is greater than or equal to the total cost, the last chosen candidate is the valid starting point.

The function canCompleteCircuit iterates over the gas stations. It calculates the totalGas and totalCost along the way. While computing the running balance currentGas, if it becomes negative, the potential start index is updated to the next station. After the loop, if totalGas is greater than or equal to totalCost, it returns the last updated starting index; otherwise, it returns -1.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of stations.
Space Complexity: O(1), as extra space used is constant.

Try this approach in the editor →

Approach 2: Brute Force Approach

This approach attempts to simulate the journey starting from each station. For each potential start, check if the car can complete the circuit using the available gas at each station. While this approach may be easier to understand, it is inefficient because it checks each station iteratively, leading to potentially high computational costs for longer arrays. It is not recommended for larger datasets but can be useful for understanding how the journey works preliminarily.

This brute force method checks every gas station as a candidate for starting point. It uses the variable currentGas to simulate the journey to verify whether each one can be completed in a circle. If at any point the gas becomes insufficient, the loop breaks early, and the next station is checked as a potential start.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) due to double iteration.
Space Complexity: O(1) as no extra space is utilized.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time Complexity: O(n), where n is the number of stations.
Space Complexity: O(1), as extra space used is constant.

Brute Force Approach

Time Complexity: O(n^2) due to double iteration.
Space Complexity: O(1) as no extra space is utilized.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(n²)O(1)Useful for understanding the circular traversal logic or validating small inputs
Greedy Single PassO(n)O(1)Optimal approach for interviews and production due to linear scan and constant memory

Video Solution

Gas Station - Greedy - Leetcode 134 - Python • NeetCode • 219,839 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Gas Station easy or hard?
Gas Station is generally classified as a Medium problem. The implementation is simple once the greedy insight is known, but recognizing why failed segments can be skipped requires careful reasoning about cumulative fuel deficits.
Gas Station Python/Java solution
The greedy implementation is nearly identical across languages. Iterate through the arrays, maintain total and current fuel balances, and reset the candidate start when the running tank becomes negative. This logic works the same in Python, Java, C++, C#, JavaScript, and C.
How to solve Gas Station in O(n)?
First compute a running difference of gas minus cost while iterating through the stations. Maintain a current tank and a candidate starting index. If the current tank drops below zero at station i, reset the start to i + 1 and reset the tank. If the total gas minus cost across the array is non‑negative, the final start index completes the circuit.
What is the best approach for Gas Station?
The optimal approach is a greedy single-pass algorithm. Track the total gas balance and a running tank while scanning the array. Whenever the running tank becomes negative, reset the starting station to the next index. This approach runs in O(n) time and O(1) space.
Is Gas Station asked at Google/Amazon/Meta?
Gas Station is a common greedy interview problem and has appeared in interviews at companies like Amazon, Google, and other large tech firms. It tests reasoning about cumulative sums, greedy decisions, and array traversal.
What data structure is used in Gas Station?
The problem primarily uses arrays and simple integer variables for cumulative tracking. No advanced data structures are required; the key idea is maintaining running sums and applying a greedy reset rule during array traversal.
What is the time complexity of Gas Station?
The optimal greedy solution runs in O(n) time because the array is scanned exactly once. The brute force approach takes O(n^2) time since it simulates a full circular trip for every possible starting station.

Ready to solve this problem?

Practice Gas Station with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximize the Topmost Element After K Moves