Neetcode 150 - Gas Station

1. Input, Output, Contraints

  1. Input:
  • gas[i] — amount of gas at station i
  • cost[i] — gas needed to travel from station i to (i + 1) % n

=> n == len(gas) == len(cost)

  1. Output:

  • Index of the starting gas station (0-indexed) => If you can travel around once in the clockwise direction and return to start

  • Return -1 if impossible.

  1. Constraints:

  • 1 ≤ n ≤ 10^5

  • 0 ≤ gas[i], cost[i] ≤ 10^4

2. Dry run

i	gas[i]	cost[i]	gain (gas[i]-cost[i])	tank	total	start	Action
0	1	3	-2	-2	-2	1	tank < 0 → reset start=1
1	2	4	-2	-2	-4	2	tank < 0 → reset start=2
2	3	5	-2	-2	-6	3	tank < 0 → reset start=3
3	4	1	+3	3	-3	3	tank >= 0
4	5	2	+3	6	0	3	✅ end

3. Solution 1: Naive Approach O(N^2)

def canCompleteCircuit(gas, cost):
    n = len(gas)
    for start in range(n):
        tank = 0
        count = 0
        while count < n:
            i = (start + count) % n
            tank += gas[i] - cost[i]
            if tank < 0:
                break  # cannot continue
            count += 1
        if count == n:
            return start
    return -1
  • Time Complexity: O(N^2)
  • Space Complexity: O(1)

=> Cover all cases of result

4. Solution 2: Optimal Solution O(N)

def canCompleteCircuit(gas, cost):
    total = 0
    tank = 0
    start = 0
    for i in range(len(gas)):
        gain = gas[i] - cost[i]
        total += gain
        tank += gain
        if tank < 0:            # cannot reach next station
            start = i + 1       # skip to next candidate
            tank = 0
    return start if total >= 0 else -1
  • Time Complexity: O(N)
  • Space Complexity: O(1)

=> Notes: Total has been calculated total - gain before and we need to check at the final do it go through all the stations.

October 14, 2025