leetcode/apps/docs/content/(05-decision-space)/greedy/134_gas-station.mdx

---
title: '134. Gas Station'
description: There are n gas stations along a circular route, where the amount of gas at the i^th station is gas[i]
icon: dot
topics:
  - { name: "Array", slug: "array" }
  - { name: "Greedy", slug: "greedy" }
issue: "https://github.com/prdlk/leetcode/issues/176"
companies:
  - { name: "Bloomberg", period: "Thirty Days", frequency: 69.8 }
  - { name: "Sprinklr", period: "Three Months", frequency: 95.9 }
  - { name: "TikTok", period: "Three Months", frequency: 70.9 }
  - { name: "Microsoft", period: "Three Months", frequency: 33.4 }
  - { name: "Amazon", period: "Three Months", frequency: 28.9 }
  - { name: "Adobe", period: "Six Months", frequency: 74.3 }
  - { name: "Goldman Sachs", period: "Six Months", frequency: 44.8 }
  - { name: "Google", period: "Six Months", frequency: 17.4 }
sidebar:
  label: 'Gas Station'
  badge: 'Medium'
---

### 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^5`
- `0 <= gas[i], cost[i] <= 10^4`
- The input is generated such that the answer is unique.

## Solution

```py
class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        start, tank, total = 0, 0, 0

        for i in range(len(gas)):
            drive = gas[i] - cost[i]
            tank = tank + drive

            if tank < 0:
                tank = 0
                start = i + 1
            total = total + drive

        return start if total >= 0 else -1
```