Gas Station
MediumIf total gas ≥ cost, the deficit point is the start
If the total gas is enough, start right after the point where you'd run emptiest.
The idea
If total gas covers total cost, a solution exists and is unique. Track a running tank; whenever it goes negative, no start before the next station works, so restart there.
Step 1 of 7. Each cell is gas − cost at that station. If total is non-negative a solution exists; find where the tank never dips below zero. Values: -2, -2, -2, 3, 3. Pointers: start at index 0. tank 0, total 0.
Reset start on deficit.
1let total = 0, tank = 0, start = 0;2for (let i = 0; i < n; i++) {3 const d = gas[i] - cost[i];4 total += d; tank += d;5 if (tank < 0) { start = i + 1; tank = 0; }6}7return total >= 0 ? start : -1;Input
- array
- [-2, -2, -2, 3, 3]
Memory
- start
- = 0 [-2]
- i
- —
- tank
- 0
- total
- 0
Output
- tank
- 0
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
- Output:
- 3
- Explanation:
- Starting at station 3 lets you complete the loop.
Example 2
- Input:
- gas = [2, 3, 4], cost = [3, 4, 3]
- Output:
- -1
- Explanation:
- Total gas < total cost → -1.
Example 3
- Input:
- gas = [5, 1, 2, 3, 4], cost = [4, 4, 1, 5, 1]
- Output:
- 4
- Explanation:
- Start at station 4.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.