134. Gas Station - Solution & Explanation

The problem

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⁴

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.

Python

def canCompleteCircuit(gas, cost):
    totalGas, totalCost = 0, 0
    start, currentGas = 0, 0

    for i in range(len(gas)):
        totalGas += gas[i]
        totalCost += cost[i]
        currentGas += gas[i] - cost[i]

        if currentGas < 0:
            start = i + 1
            currentGas = 0

    return start if totalGas >= totalCost else -1


gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(canCompleteCircuit(gas, cost))

Java

public class GasStation {
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0, totalCost = 0, start = 0, currentGas = 0;
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            currentGas += gas[i] - cost[i];
            if (currentGas < 0) {
                start = i + 1;
                currentGas = 0;
            }
        }
        return totalGas >= totalCost ? start : -1;
    }

    public static void main(String[] args) {
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};
        System.out.println(canCompleteCircuit(gas, cost));
    }
}

C++

#include <vector>
#include <iostream>

int canCompleteCircuit(std::vector<int>& gas, std::vector<int>& cost) {
    int totalGas = 0, totalCost = 0, start = 0, currentGas = 0;
    for (int i = 0; i < gas.size(); i++) {
        totalGas += gas[i];
        totalCost += cost[i];
        currentGas += gas[i] - cost[i];
        if (currentGas < 0) {
            start = i + 1;
            currentGas = 0;
        }
    }
    return totalGas >= totalCost ? start : -1;
}

int main() {
    std::vector<int> gas = {1, 2, 3, 4, 5};
    std::vector<int> cost = {3, 4, 5, 1, 2};
    int result = canCompleteCircuit(gas, cost);
    std::cout << result << std::endl;
    return 0;
}

JavaScript

function canCompleteCircuit(gas, cost) {
    let totalGas = 0, totalCost = 0;
    let start = 0, currentGas = 0;

    for (let i = 0; i < gas.length; i++) {
        totalGas += gas[i];
        totalCost += cost[i];
        currentGas += gas[i] - cost[i];

        if (currentGas < 0) {
            start = i + 1;
            currentGas = 0;
        }
    }
    return totalGas >= totalCost ? start : -1;
}

let gas = [1, 2, 3, 4, 5];
let cost = [3, 4, 5, 1, 2];
console.log(canCompleteCircuit(gas, cost));

#include <stdio.h>

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
    int totalGas = 0, totalCost = 0, start = 0, currentGas = 0;
    for (int i = 0; i < gasSize; i++) {
        totalGas += gas[i];
        totalCost += cost[i];
        currentGas += gas[i] - cost[i];
        if (currentGas < 0) {
            start = i + 1;
            currentGas = 0;
        }
    }
    return totalGas >= totalCost ? start : -1;
}

int main() {
    int gas[] = {1, 2, 3, 4, 5};
    int cost[] = {3, 4, 5, 1, 2};
    int result = canCompleteCircuit(gas, 5, cost, 5);
    printf("%d\n", result);
    return 0;
}

using System;

class Program {
    public static int CanCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0, totalCost = 0, start = 0, currentGas = 0;

        for (int i = 0; i < gas.Length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            currentGas += gas[i] - cost[i];

            if (currentGas < 0) {
                start = i + 1;
                currentGas = 0;
            }
        }

        return totalGas >= totalCost ? start : -1;
    }

    static void Main(string[] args) {
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};
        int result = CanCompleteCircuit(gas, cost);
        Console.WriteLine(result);
    }
}

In Python, the function iterates through the gas stations and calculates both the total gas and the total cost. The variable currentGas keeps track of the difference between gas and cost. Reset the start index whenever this balance turns negative. If the total gas is sufficient to meet all costs, the function returns the most recently identified start; otherwise, it returns -1.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

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.

Python

def canCompleteCircuit(gas, cost):
    n = len(gas)
    for start in range(n):
        currentGas = 0
        count = 0

        while count < n:
            index = (start + count) % n
            currentGas += gas[index] - cost[index]
            if currentGas < 0:
                break
            count += 1

        if count == n:
            return start
    return -1


gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(canCompleteCircuit(gas, cost))

Java

public class GasStation {
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        for (int start = 0; start < gas.length; start++) {
            int currentGas = 0;
            int count = 0;

            while (count < gas.length) {
                int index = (start + count) % gas.length;
                currentGas += gas[index] - cost[index];
                if (currentGas < 0) break;
                count++;
            }

            if (count == gas.length) return start;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};
        System.out.println(canCompleteCircuit(gas, cost));
    }
}

C++

#include <vector>
#include <iostream>

int canCompleteCircuit(std::vector<int>& gas, std::vector<int>& cost) {
    int n = gas.size();
    for (int start = 0; start < n; start++) {
        int currentGas = 0;
        int count = 0;

        while (count < n) {
            int index = (start + count) % n;
            currentGas += gas[index] - cost[index];
            if (currentGas < 0) break;
            count++;
        }

        if (count == n) return start;
    }
    return -1;
}

int main() {
    std::vector<int> gas = {1, 2, 3, 4, 5};
    std::vector<int> cost = {3, 4, 5, 1, 2};
    int result = canCompleteCircuit(gas, cost);
    std::cout << result << std::endl;
    return 0;
}

JavaScript

function canCompleteCircuit(gas, cost) {
    let n = gas.length;
    for (let start = 0; start < n; start++) {
        let currentGas = 0;
        let count = 0;

        while (count < n) {
            let index = (start + count) % n;
            currentGas += gas[index] - cost[index];
            if (currentGas < 0) break;
            count++;
        }

        if (count === n) return start;
    }
    return -1;
}

let gas = [1, 2, 3, 4, 5];
let cost = [3, 4, 5, 1, 2];
console.log(canCompleteCircuit(gas, cost));

#include <stdio.h>

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
    for (int start = 0; start < gasSize; start++) {
        int currentGas = 0;
        int count = 0;

        while (count < gasSize) {
            int index = (start + count) % gasSize;
            currentGas += gas[index] - cost[index];
            if (currentGas < 0) break;
            count++;
        }

        if (count == gasSize) return start;
    }
    return -1;
}

int main() {
    int gas[] = {1, 2, 3, 4, 5};
    int cost[] = {3, 4, 5, 1, 2};
    int result = canCompleteCircuit(gas, 5, cost, 5);
    printf("%d\n", result);
    return 0;
}

using System;

class Program {
    public static int CanCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.Length;
        for (int start = 0; start < n; start++) {
            int currentGas = 0;
            int count = 0;

            while (count < n) {
                int index = (start + count) % n;
                currentGas += gas[index] - cost[index];
                if (currentGas < 0) break;
                count++;
            }

            if (count == n) return start;
        }
        return -1;
    }

    static void Main(string[] args) {
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};
        int result = CanCompleteCircuit(gas, cost);
        Console.WriteLine(result);
    }
}

The Python solution uses an iterative brute force algorithm to evaluate each possible starting station. It tests whether a full circuit is possible starting from each index. Any failure results in immediate exit from the loop, and the next index is assessed.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function canCompleteCircuit(gas: number[], cost: number[]): number {
    const n = gas.length;
    let i = n - 1;
    let j = n - 1;
    let s = 0;
    let cnt = 0;
    while (cnt < n) {
        s += gas[j] - cost[j];
        ++cnt;
        j = (j + 1) % n;
        while (s < 0 && cnt < n) {
            --i;
            s += gas[i] - cost[i];
            ++cnt;
        }
    }
    return s < 0 ? -1 : i;
}

func canCompleteCircuit(gas []int, cost []int) int {
	n := len(gas)
	i, j := n-1, n-1
	cnt, s := 0, 0
	for cnt < n {
		s += gas[j] - cost[j]
		cnt++
		j = (j + 1) % n
		for s < 0 && cnt < n {
			i--
			s += gas[i] - cost[i]
			cnt++
		}
	}
	if s < 0 {
		return -1
	}
	return i
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach	Time Complexity: O(n) Space Complexity: O(1)
Brute Force Approach	Time Complexity: O(n^2) Space Complexity: O(1)
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Simulation	O(n²)	O(1)	Useful for understanding the circular traversal logic or validating small inputs
Greedy Single Pass	O(n)	O(1)	Optimal approach for interviews and production due to linear scan and constant memory

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.

Gas Station solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Brute Force Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Gas Station solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Brute Force Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems