Log inSign up
mediumLeetCodeNot Started

Gas Station

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

There are n gas stations along a circular route. At station i, you get gas[i] units of fuel, and it costs cost[i] units to travel to station (i + 1) % n. You start with an empty tank at one station.

Return the 0-indexed starting station index from which you can complete the entire clockwise circuit, or -1 if impossible. The solution is guaranteed to be unique if it exists.

Example 1 · Example 1: Circuit Complete from Station 3:

Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Explanation: Start at station 3 (index 3):\n- Fill 4 units. Tank = 4. Cost to station 4 is 1. Tank = 3.\n- Fill 5 units. Tank = 8. Cost to station 0 is 2. Tank = 6.\n- Fill 1 unit. Tank = 7. Cost to station 1 is 3. Tank = 4.\n- Fill 2 units. Tank = 6. Cost to station 2 is 4. Tank = 2.\n- Fill 3 units. Tank = 5. Cost to station 3 is 5. Tank = 0. Completed loop!

Example 2 · Example 2: Impossible Circuit:

Input: gas = [2, 3, 4], cost = [3, 4, 3]
Output: -1
Explanation: Total gas = 2 + 3 + 4 = 9. Total cost = 3 + 4 + 3 = 10. Since total gas < total cost, it is impossible to complete circuit.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Prove why resetting the candidate start to i + 1 is correct.
  • Understand circular array traversal invariants.
  • Implement the single-pass greedy solution across 4 languages.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Circular route with gains and costs at each node.
  • Find a starting position that maintains a non-negative running balance throughout the cycle.
  • Total sum determines overall existence of a valid solution.

Algorithmic Decision Tree:

  • Check totalGas >= totalCost first.
  • Accumulate currentTank: when currentTank < 0, advance start to i + 1 and reset currentTank.

Connected Patterns:

CandyContinuous Subarray SumJump Game

1. Brute Force — Simulate Each Starting Station

Intuition

Try starting at every station i from 0 to N - 1. Maintain tank. Move to (j + 1) % N. If tank ever becomes negative, break and try next station. If we complete N steps, return i. If no station works, return -1.

When to apply: When N <= 500.

Algorithm

  1. Step 1: Loop start from 0 to N - 1.
  2. Step 2: Set tank = 0, steps = 0, j = start.
  3. Step 3: While steps < N: tank += gas[j] - cost[j]. If tank < 0 break. Advance j = (j + 1) % N, steps++.
  4. Step 4: If steps == N, return start.
  5. Step 5: Return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
9 int n = gas.size();
10 for (int start = 0; start < n; ++start) {
11 int tank = 0;
12 int steps = 0;
13 int j = start;
14 while (steps < n) {
15 tank += gas[j] - cost[j];
16 if (tank < 0) break;
17 j = (j + 1) % n;
18 steps++;
19 }
20 if (steps == n) return start;
21 }
22 return -1;
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<int> gas = {1, 2, 3, 4, 5};
29 vector<int> cost = {3, 4, 5, 1, 2};
30 cout << "Start station: " << sol.canCompleteCircuit(gas, cost) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N^2) — N candidate starts, each potentially simulating N steps.
  • Space complexity: O(1) — Scalar integer variables only.

Why Brute Force Doesn't Scale:

With N = 105, N2 is 1010 operations, which severely times out. The greedy single pass runs in ~10ms.

For N = 100,000: O(N) requires exactly 100,000 iterations, finishing in ~5ms.

2. Better — Prefix Sum Valley Analysis

Intuition

Let diff[i] = gas[i] - cost[i]. Compute running prefix sum of diff. If total sum < 0, impossible. Otherwise, find the index minIdx where prefix sum is minimum. The station minIdx + 1 starts the journey at the lowest potential, ensuring all subsequent prefix sums remain non-negative.

When to apply: When understanding the mathematical prefix-sum valley concept.

Algorithm

  1. Step 1: Compute total net difference sum(gas) - sum(cost). If < 0, return -1.
  2. Step 2: Track running sum and record minIdx where running sum reaches minimum.
  3. Step 3: Return (minIdx + 1) % N.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
9 int n = gas.size();
10 int total = 0;
11 int minSum = 1e9;
12 int minIdx = -1;
13 int running = 0;
14
15 for (int i = 0; i < n; ++i) {
16 int diff = gas[i] - cost[i];
17 total += diff;
18 running += diff;
19 if (running < minSum) {
20 minSum = running;
21 minIdx = i;
22 }
23 }
24 return total < 0 ? -1 : (minIdx + 1) % n;
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<int> gas = {1, 2, 3, 4, 5};
31 vector<int> cost = {3, 4, 5, 1, 2};
32 cout << "Start station: " << sol.canCompleteCircuit(gas, cost) << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass computing running sum and tracking minimum.
  • Space complexity: O(1) — Scalar integer variables.

3. Optimal — Single-Pass Greedy Tank Reset

Intuition

Keep totalSurplus and currentTank. For each station i, update both with (gas[i] - cost[i]). If currentTank < 0, it means the current candidate start cannot reach i + 1, so reset start = i + 1 and currentTank = 0. At the end, if totalSurplus >= 0 return start, else return -1.

When to apply: Standard optimal interview solution for Gas Station.

Algorithm

  1. Step 1: Initialize totalSurplus = 0, currentTank = 0, start = 0.
  2. Step 2: Iterate i from 0 to N - 1.
  3. Step 3: totalSurplus += gas[i] - cost[i], currentTank += gas[i] - cost[i].
  4. Step 4: If currentTank < 0: set start = i + 1 and currentTank = 0.
  5. Step 5: Return totalSurplus >= 0 ? start : -1.

Interactive Trace for Gas Station

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: At i=0, gas[0]=1, cost[0]=3
Visual state
Values and pointers at this exact step
pointers
S
diff: -2
diff: -2
diff: -2
diff: +3
diff: +3
0
1
↑ reset_to
2
3
4
Check / comparison
1 - 3 = -2 < 0 (Tank deficit)
Decision / next transition
Reset start = 1, tank = 0.
Why this step matters

Step 1: At i=0, gas[0]=1, cost[0]=3. tank becomes -2. Negative!

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
9 int totalSurplus = 0;
10 int currentTank = 0;
11 int start = 0;
12
13 for (int i = 0; i < gas.size(); ++i) {
14 totalSurplus += gas[i] - cost[i];
15 currentTank += gas[i] - cost[i];
16
17 if (currentTank < 0) {
18 start = i + 1;
19 currentTank = 0;
20 }
21 }
22 return totalSurplus >= 0 ? start : -1;
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<int> gas = {1, 2, 3, 4, 5};
29 vector<int> cost = {3, 4, 5, 1, 2};
30 cout << "Start station: " << sol.canCompleteCircuit(gas, cost) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass over the N stations.
  • Space complexity: O(1) auxiliary — Uses only three integer variables: totalSurplus, currentTank, start.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Simulate Each Starting StationO(N^2)O(1)Test every station i as start, simulating loop until tank < 0 or completed.Repeated full-cycle simulations.
2.Better — Prefix Sums Array and Valley FindingO(N)O(N)Calculate prefix sums of (gas[i] - cost[i]). If total < 0 return -1. Otherwise, the station right after the minimum prefix sum valley is the start.Array memory allocation.
3.Optimal — Single-Pass Greedy Tank ResetOptimalO(N)O(1) auxiliaryMaintain totalSurplus and currentTank. If currentTank < 0 at i, reset start = i + 1 and currentTank = 0. Return totalSurplus >= 0 ? start : -1.None.

Common Pitfalls & Crucial Edge Cases

Simulating circularly past N in the greedy approach

A second pass is completely unnecessary because totalSurplus >= 0 mathematically guarantees the remaining loop completes.

Resetting start to start + 1 instead of i + 1

Any intermediate station between start and i had positive incoming fuel, so starting there with 0 fuel would fail even earlier.

Crucial Edge Cases to Validate:

  • N = 1 — If gas[0] >= cost[0], returns 0; else -1.
  • Total gas exactly equals total cost — Valid unique start station exists.
  • All gas[i] < cost[i] — Returns -1.
  • Start station is index 0 — Loops through entire array without tank ever dipping below 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the two key insights clearly: (1) sum(gas) >= sum(cost) guarantees a solution exists, (2) failure at station i allows jumping candidate start to i + 1.
  2. Interviewers frequently ask for the proof of why start to i can be skipped.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can we safely skip all intermediate stations between start and i when the tank runs dry at i?

Back to DSA Sheet