Gas Station

Med

#0134Time: O(N^2)Space: O(1)16 companies

Patterns

Greedy

Data structures

Array

Companies

BNY Mellon Cisco Flipkart Goldman Sachs

Prompt

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

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i^th 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 <= 10⁵
0 <= gas[i], cost[i] <= 10⁴
The input is generated such that the answer is unique.

Approaches

2 approaches with complexity analysis and trade-offs.

The most intuitive approach is to try every gas station as a potential starting point. For each starting station, we simulate the entire circular journey to see if it's possible to complete it without the gas tank ever becoming negative.

Algorithm

Loop through each station i from 0 to n-1.
Inside the loop, assume i is the starting station. Initialize tank = 0.
Start a nested loop to simulate the journey for n steps.
In each step k, the current station index will be j = (i + k) % n.
Update the tank: tank += gas[j] - cost[j].
If tank < 0, break the inner loop as this starting point i is not feasible.
If the inner loop completes all n steps successfully, it means a full circle was made. Return i.
If the outer loop finishes without returning, it means no solution was found. Return -1.

Walkthrough

This method iterates through each of the n gas stations, considering each one as a potential starting point. For a given starting station i, we simulate the journey by moving clockwise around the circuit. We maintain a tank variable, which represents the current amount of gas in the car. At each station j in the simulated path, we add gas[j] and subtract cost[j]. If the tank ever drops below zero, it means we cannot reach the next station, so this starting point i is invalid. We then abandon this simulation and try the next potential starting station i+1. If we successfully complete a full circle of n stations without the tank becoming negative, we have found our answer, and we return the starting index i. If we try all n stations as starting points and none of them allow for a complete circuit, it means no solution exists, and we return -1.

1class Solution {2    public int canCompleteCircuit(int[] gas, int[] cost) {3        int n = gas.length;4        for (int i = 0; i < n; i++) {5            int tank = 0;6            // We need to check for a full circle, so we check n stations7            for (int j = 0; j < n; j++) {8                int currentStation = (i + j) % n;9                tank += gas[currentStation] - cost[currentStation];10                if (tank < 0) {11                    // This starting point is not possible, break and try the next one12                    break;13                }14            }15            // If the inner loop completed without tank going negative, we found the solution16            if (tank >= 0) {17                return i;18            }19        }20        return -1;21    }22}

Complexity

Time

O(N^2)

Space

O(1)

Trade-offs

Pros

Simple to understand and implement.
Correctly solves the problem for all cases.

Cons

Inefficient for large inputs due to its quadratic time complexity.

A more efficient approach leverages a key insight: if the total gas available is less than the total cost to travel, no solution is possible. Conversely, if the total gas is sufficient, a unique solution is guaranteed to exist. We can find this solution in a single pass by keeping track of the current fuel tank level and identifying the correct starting point.

Algorithm

Initialize total_tank = 0, current_tank = 0, and start_station = 0.
Iterate through the stations from i = 0 to n-1.
For each station i, calculate the net gas change: gas[i] - cost[i].
Add this change to both total_tank and current_tank.
If current_tank becomes negative, it means we cannot reach station i+1 from the current start_station.
Update our potential starting point to be the next station: start_station = i + 1.
Reset current_tank to 0, as we are starting a new journey attempt from this new start_station.
After the loop, check if total_tank is non-negative. If it is, a solution exists, and start_station is the answer. Otherwise, no solution exists.
Return start_station if total_tank >= 0, else return -1.

Walkthrough

This approach is based on two main observations:

If sum(gas) < sum(cost), it's impossible to complete the circuit. We can check this first. If this condition is met, we can immediately return -1.
If we start at a station i and run out of gas before reaching station j, it means we cannot start at any station between i and j either. This is because if we started at any station k (where i <= k < j), we would have had less fuel when arriving at j than if we had started at i (since the journey from i to k-1 was possible, meaning the net gas gain was non-negative). Therefore, if we fail at j, we must try a starting point after j, specifically j+1.

We can solve this problem in a single pass. We maintain a current_tank variable to track the gas from a potential starting point (start_station). We also maintain a total_tank to check the overall feasibility.

1class Solution {2    public int canCompleteCircuit(int[] gas, int[] cost) {3        int n = gas.length;4        int total_tank = 0;5        int current_tank = 0;6        int start_station = 0;7 8        for (int i = 0; i < n; i++) {9            total_tank += gas[i] - cost[i];10            current_tank += gas[i] - cost[i];11 12            // If we can't reach the next station from the current start_station13            if (current_tank < 0) {14                // Pick the next station as the new starting point15                start_station = i + 1;16                // Reset the current tank for the new journey17                current_tank = 0;18            }19        }20 21        // If the total gas is greater than or equal to the total cost, a solution exists.22        // The 'start_station' found is the answer. Otherwise, no solution.23        return total_tank >= 0 ? start_station : -1;24    }25}

Complexity

Time

O(N)

Space

O(1)

Trade-offs

Pros

Highly efficient with linear time complexity.
Requires constant extra space.
Solves the problem in a single pass.

Cons

The logic is less intuitive than the brute-force approach and relies on a greedy proof.

Solutions

Solution

1public class Solution {2    public int CanCompleteCircuit(int[] gas, int[] cost) {3        int n = gas.Length;4        int i = n - 1, j = n - 1;5        int s = 0, cnt = 0;6        while (cnt < n) {7            s += gas[j] - cost[j];8            ++cnt;9            j = (j + 1) % n;10            while (s < 0 && cnt < n) {11                --i;12                s += gas[i] - cost[i];13                ++cnt;14            }15        }16        return s < 0 ? -1 : i;17    }18}

1class Solution {2public3  int canCompleteCircuit(int[] gas, int[] cost) {4    int n = gas.length;5    int i = n - 1, j = n - 1;6    int cnt = 0, s = 0;7    while (cnt < n) {8      s += gas[j] - cost[j];9      ++cnt;10      j = (j + 1) % n;11      while (s < 0 && cnt < n) {12        --i;13        s += gas[i] - cost[i];14        ++cnt;15      }16    }17    return s < 0 ? -1 : i;18  }19}

1class Solution {2public:3  int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {4    int n = gas.size();5    int i = n - 1, j = n - 1;6    int cnt = 0, s = 0;7    while (cnt < n) {8      s += gas[j] - cost[j];9      ++cnt;10      j = (j + 1) % n;11      while (s < 0 && cnt < n) {12        --i;13        s += gas[i] - cost[i];14        ++cnt;15      }16    }17    return s < 0 ? -1 : i;18  }19};

1class Solution : def canCompleteCircuit ( self , gas : List [ int ], cost : List [ int ]) -> int : n = len ( gas ) i = j = n - 1 cnt = s = 0 while cnt < n : s += gas [ j ] - cost [ j ] cnt += 1 j = ( j + 1 ) % n while s < 0 and cnt < n : i -= 1 s += gas [ i ] - cost [ i ] cnt += 1 return - 1 if s < 0 else i

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem