Gas Station
On this page
Problem statement
n gas stations stand on a circular road. At station i you can pick up
gas[i]units of fuel, and driving from station i to station i + 1 (from the last station back to station 0) burnscost[i]units. Your car starts with an empty tank of unlimited size. Return the index of a station from which you can drive all the way around once, or −1 if there is none. When a solution exists, it is unique.
A greedy problem with a one-pass answer that sounds too simple until you can say why it works. Original problem: LeetCode 134.
Example

Input: gas = [2, 5, 1, 4, 3]
cost = [3, 2, 4, 1, 3]
Output: 1
Input: gas = [1, 2], cost = [2, 2] -> -1 # 3 units of gas, 4 needed
Constraints (assumed)
- 1 ≤ n ≤ 10⁵; 0 ≤ gas[i], cost[i] ≤ 10⁴.
What this question tests
- Reducing the problem to one array of gains
gas[i] − cost[i]. - The two greedy facts: enough total gas means some start works, and a failed run rules out every station inside it.
- Turning an O(n²) simulation into one pass.
Questions to ask first
- Is the answer unique? (Here: yes, if one exists.)
- Does the tank start empty? (Here: yes, and you fill up at the start station first.)
- Which direction? (Here: i to i + 1 only.)
- Is arriving with exactly 0 fuel OK? (Here: yes; only negative fuel fails.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.