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.length1 <= n <= 1050 <= gas[i], cost[i] <= 104Problem Overview: You are given two arrays gas and cost. gas[i] is the fuel available at station i, and cost[i] is the fuel required to travel from station i to i+1. The stations form a circle. Your task is to return the index of the station where you can start with an empty tank and complete the full loop without running out of gas. If it’s impossible, return -1.
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 start index, maintain a running tank value. Add gas[i], subtract cost[i], and move to the next station using circular indexing. If the tank ever becomes negative, that start index fails. Continue until either a full loop succeeds or all stations are tested. This method directly models the problem and helps verify correctness, but it repeatedly rechecks the same segments, leading to quadratic time complexity.
Approach 2: Greedy Single Pass (O(n) time, O(1) space)
The optimal solution relies on a greedy observation. If the total gas across all stations is less than the total travel cost, completing the circuit is impossible. Otherwise, exactly one valid starting point exists. Iterate through the array once while tracking a running tank value. If the tank becomes negative at station i, none of the stations from the current start up to i can be valid starting points. Reset the start to i + 1 and reset the tank to zero. Continue scanning until the end.
The key insight: if a segment from start to i fails, every station inside that segment would fail even earlier. Skipping them avoids redundant checks. This makes the algorithm linear. The technique is a classic greedy strategy where you discard impossible prefixes and keep only the best candidate start.
During the same pass, maintain a totalGas - totalCost check. If the global sum is negative, return -1. Otherwise the tracked start index is guaranteed to complete the circuit.
Recommended for interviews: The greedy O(n) solution is what interviewers expect. It shows you can recognize when local failures eliminate multiple candidates and apply a greedy invariant to reduce the search space. The brute force simulation is still useful to mention briefly because it demonstrates the baseline reasoning before optimizing.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of stations.
Space Complexity: O(1), as extra space used is constant.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) due to double iteration.
Space Complexity: O(1) as no extra space is utilized.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), where n is the number of stations. |
| Brute Force Approach | Time Complexity: O(n^2) due to double iteration. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n²) | O(1) | Useful for understanding the circular traversal logic or verifying correctness on small inputs |
| Greedy Single Pass | O(n) | O(1) | Best general solution for interviews and production due to linear scan and constant memory |
BS-20. Minimise Maximum Distance between Gas Stations | 3 Approaches | Heap | Binary Search • take U forward • 192,502 views views
Watch 9 more video solutions →Practice Gas Station with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor