Gas Station

LeetCode problem #134

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

You are given two integer arrays gas and cost, each of length n, representing a circular route of n gas stations:

gas[i] = amount of gas you can pick up at station i
cost[i] = amount of gas required to travel from station i to station (i + 1) % n

You start the journey with an empty tank at one station of your choice. At each station, you may refuel (add gas[i]), then you must pay cost[i] to travel to the next station.

Return the starting station index if you can travel around the circuit exactly once (visit every station and return to the start). If it’s impossible, return -1.

Input / Output Format

Input: two arrays gas, cost (same length n)
Output: an integer index in [0, n-1] or -1

Constraints

n == gas.length == cost.length
1 <= n <= 10^5
0 <= gas[i], cost[i] <= 10^4

Examples

Example 1

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation: Start at station 3:

tank=0+4-1=3
at 4: tank=3+5-2=6
at 0: tank=6+1-3=4
at 1: tank=4+2-4=2
at 2: tank=2+3-5=0 (completed)

Example 2

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation: Total gas = 9, total cost = 10, so it’s impossible from any start.

Example 3 (Edge-ish: single station)

Input: gas = [5], cost = [4]
Output: 0
Explanation: You can refuel 5 and spend 4 to return to itself.

Edge Cases to Notice

Total gas < total cost ⇒ always -1
Multiple valid starts may exist; the problem guarantees uniqueness in typical LeetCode statement, but your solution should still return a valid one
gas[i] == cost[i] everywhere ⇒ any index works (optimized algorithm returns 0)

Approach 1: Brute Force

Algorithm Explanation

Try each station start from 0..n-1:

Set tank = 0
Simulate traveling n steps:
- tank += gas[curr]
- if tank < cost[curr], fail this start
- else tank -= cost[curr], move to next station
If you complete n moves, return start

This is straightforward but can be too slow for n = 10^5.

Python (Brute Force)

from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if gas is None or cost is None or len(gas) != len(cost):
            return -1
        n = len(gas)
        if n == 0:
            return -1

        for start in range(n):
            tank = 0
            ok = True
            for step in range(n):
                i = (start + step) % n
                tank += gas[i]
                if tank < cost[i]:
                    ok = False
                    break
                tank -= cost[i]
            if ok:
                return start
        return -1

Java (Brute Force)

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas == null || cost == null || gas.length != cost.length) return -1;
        int n = gas.length;
        if (n == 0) return -1;

        for (int start = 0; start < n; start++) {
            int tank = 0;
            boolean ok = true;
            for (int step = 0; step < n; step++) {
                int i = (start + step) % n;
                tank += gas[i];
                if (tank < cost[i]) {
                    ok = false;
                    break;
                }
                tank -= cost[i];
            }
            if (ok) return start;
        }
        return -1;
    }
}

Go (Brute Force)

package main

func canCompleteCircuit(gas []int, cost []int) int {
	if gas == nil || cost == nil || len(gas) != len(cost) || len(gas) == 0 {
		return -1
	}
	n := len(gas)

	for start := 0; start < n; start++ {
		tank := 0
		ok := true
		for step := 0; step < n; step++ {
			i := (start + step) % n
			tank += gas[i]
			if tank < cost[i] {
				ok = false
				break
			}
			tank -= cost[i]
		}
		if ok {
			return start
		}
	}
	return -1
}

JavaScript (Brute Force)

/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
function canCompleteCircuit(gas, cost) {
  if (!Array.isArray(gas) || !Array.isArray(cost) || gas.length !== cost.length) return -1;
  const n = gas.length;
  if (n === 0) return -1;

  for (let start = 0; start < n; start++) {
    let tank = 0;
    let ok = true;
    for (let step = 0; step < n; step++) {
      const i = (start + step) % n;
      tank += gas[i];
      if (tank < cost[i]) {
        ok = false;
        break;
      }
      tank -= cost[i];
    }
    if (ok) return start;
  }
  return -1;
}

C# (Brute Force)

using System;

public class Solution
{
    public int CanCompleteCircuit(int[] gas, int[] cost)
    {
        if (gas == null || cost == null || gas.Length != cost.Length) return -1;
        int n = gas.Length;
        if (n == 0) return -1;

        for (int start = 0; start < n; start++)
        {
            int tank = 0;
            bool ok = true;
            for (int step = 0; step < n; step++)
            {
                int i = (start + step) % n;
                tank += gas[i];
                if (tank < cost[i])
                {
                    ok = false;
                    break;
                }
                tank -= cost[i];
            }
            if (ok) return start;
        }
        return -1;
    }
}

Complexity Analysis (Brute Force)

Time: O(n^2) (simulate n steps for each starting station)
Space: O(1)

Approach 2: Optimized Solution

Better Algorithm Explanation (Greedy)

Key facts:

If sum(gas) < sum(cost), it’s impossible → return -1.
If you start at some station start and your running tank becomes negative at station i, then no station between start and i can be a valid start.
- Because any of those starts would have even less gas accumulated before reaching i.

Greedy procedure:

Track total += gas[i] - cost[i] over all stations (for feasibility).
Track tank += gas[i] - cost[i] as current segment balance.
If tank < 0, reset:
- start = i + 1
- tank = 0

At the end:

If total >= 0, return start
Else return -1

Python (Optimized)

from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if gas is None or cost is None or len(gas) != len(cost):
            return -1
        n = len(gas)
        if n == 0:
            return -1

        total = 0
        tank = 0
        start = 0

        for i in range(n):
            diff = gas[i] - cost[i]
            total += diff
            tank += diff
            if tank < 0:
                start = i + 1
                tank = 0

        return start if total >= 0 and start < n else -1

Java (Optimized)

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas == null || cost == null || gas.length != cost.length) return -1;
        int n = gas.length;
        if (n == 0) return -1;

        int total = 0;
        int tank = 0;
        int start = 0;

        for (int i = 0; i < n; i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            tank += diff;
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        if (total < 0 || start >= n) return -1;
        return start;
    }
}

Go (Optimized)

package main

func canCompleteCircuit(gas []int, cost []int) int {
	if gas == nil || cost == nil || len(gas) != len(cost) || len(gas) == 0 {
		return -1
	}
	n := len(gas)

	total, tank, start := 0, 0, 0
	for i := 0; i < n; i++ {
		diff := gas[i] - cost[i]
		total += diff
		tank += diff
		if tank < 0 {
			start = i + 1
			tank = 0
		}
	}
	if total < 0 || start >= n {
		return -1
	}
	return start
}

JavaScript (Optimized)

/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
function canCompleteCircuit(gas, cost) {
  if (!Array.isArray(gas) || !Array.isArray(cost) || gas.length !== cost.length) return -1;
  const n = gas.length;
  if (n === 0) return -1;

  let total = 0;
  let tank = 0;
  let start = 0;

  for (let i = 0; i < n; i++) {
    const diff = gas[i] - cost[i];
    total += diff;
    tank += diff;
    if (tank < 0) {
      start = i + 1;
      tank = 0;
    }
  }
  if (total < 0 || start >= n) return -1;
  return start;
}

C# (Optimized)

using System;

public class Solution
{
    public int CanCompleteCircuit(int[] gas, int[] cost)
    {
        if (gas == null || cost == null || gas.Length != cost.Length) return -1;
        int n = gas.Length;
        if (n == 0) return -1;

        int total = 0, tank = 0, start = 0;

        for (int i = 0; i < n; i++)
        {
            int diff = gas[i] - cost[i];
            total += diff;
            tank += diff;

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

        if (total < 0 || start >= n) return -1;
        return start;
    }
}

Complexity Analysis (Optimized)

Time: O(n) (single pass)
Space: O(1)

Key Insights

Global feasibility check: If total gas is less than total cost, no solution exists.
Greedy reset rule: When the running tank becomes negative at index i, any start in the current segment cannot work; move start to i + 1.
Why greedy is safe: The deficit at i proves you can’t reach i+1 from any earlier start in that segment because they would accumulate even less net gas before hitting the same failure point.

Edge Cases

n = 1 (single station)
Total gas equals total cost (exactly breaks even)
Many zeros: gas[i] = 0, cost[i] = 0
Immediate failure from early stations (forces multiple resets)
Start ends up being n after resets (should return -1 unless total < 0 already; we guard it)

Test Cases

Python Test Code

def run_tests():
    s = Solution()

    tests = [
        (([1,2,3,4,5], [3,4,5,1,2]), 3),
        (([2,3,4], [3,4,3]), -1),
        (([5], [4]), 0),
        (([0], [0]), 0),
        (([1,1,1], [1,1,1]), 0),
        (([3,1,1], [1,2,2]), 0),
    ]

    for (gas, cost), expected in tests:
        got = s.canCompleteCircuit(gas, cost)
        assert got == expected, (gas, cost, got, expected)

if __name__ == "__main__":
    run_tests()
    print("All tests passed.")

Java Test Code

import java.util.*;

public class Main {
    static void assertEq(int got, int expected) {
        if (got != expected) throw new AssertionError("got=" + got + " expected=" + expected);
    }

    public static void main(String[] args) {
        Solution s = new Solution();

        assertEq(s.canCompleteCircuit(new int[]{1,2,3,4,5}, new int[]{3,4,5,1,2}), 3);
        assertEq(s.canCompleteCircuit(new int[]{2,3,4}, new int[]{3,4,3}), -1);
        assertEq(s.canCompleteCircuit(new int[]{5}, new int[]{4}), 0);
        assertEq(s.canCompleteCircuit(new int[]{0}, new int[]{0}), 0);
        assertEq(s.canCompleteCircuit(new int[]{1,1,1}, new int[]{1,1,1}), 0);
        assertEq(s.canCompleteCircuit(new int[]{3,1,1}, new int[]{1,2,2}), 0);

        System.out.println("All tests passed.");
    }
}

Go Test Code

package main

import "fmt"

func assertEq(got, expected int) {
	if got != expected {
		panic(fmt.Sprintf("got=%d expected=%d", got, expected))
	}
}

func main() {
	assertEq(canCompleteCircuit([]int{1, 2, 3, 4, 5}, []int{3, 4, 5, 1, 2}), 3)
	assertEq(canCompleteCircuit([]int{2, 3, 4}, []int{3, 4, 3}), -1)
	assertEq(canCompleteCircuit([]int{5}, []int{4}), 0)
	assertEq(canCompleteCircuit([]int{0}, []int{0}), 0)
	assertEq(canCompleteCircuit([]int{1, 1, 1}, []int{1, 1, 1}), 0)
	assertEq(canCompleteCircuit([]int{3, 1, 1}, []int{1, 2, 2}), 0)

	fmt.Println("All tests passed.")
}

Common Mistakes

Forgetting the total gas vs total cost feasibility check (or equivalent total variable).
Resetting start incorrectly (should be i + 1, not i).
Not resetting tank to 0 after a failure.
Off-by-one errors with circular indexing in brute force simulation.
Returning start even when it becomes n (should return -1).

Interview Tips

Start by stating the necessary condition: sum(gas) >= sum(cost).
Explain the greedy invariant: “If I fail at i, any start before i in this segment also fails.”
Walk through a small example and show when/why start moves.
Mention complexity improvement: brute force O(n^2) vs greedy O(n).
Be explicit about corner cases (n=1, all zeros, exact balance).