Watch 10 video solutions for Gas Station, a medium level problem involving Array, Greedy. This walkthrough by take U forward has 192,502 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.
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.length1 <= n <= 1050 <= gas[i], cost[i] <= 104Problem Overview: You are given two integer arrays gas and cost. gas[i] is the fuel available at station i, and cost[i] is the fuel needed to travel from station i to i+1. The stations form a circle. Your task is to find the starting station index that allows you to complete the entire loop without running out of gas, or return -1 if it is impossible.
Approach 1: Brute Force Simulation (O(n²) time, O(1) space)
Try every station as the starting point and simulate the full trip around the circle. For each candidate start i, maintain a running tank value: add gas[j], subtract cost[j], and move to the next station using modulo to wrap around the array. If the tank ever becomes negative, that starting point fails. If you complete n steps successfully, that index is the answer. This direct simulation uses only constant extra memory but requires up to n attempts with up to n steps each, resulting in O(n²) time. It’s useful for understanding the mechanics of the circular route but does not scale well for large inputs.
Approach 2: Greedy Single Pass (O(n) time, O(1) space)
The key observation: if the total gas across all stations is less than the total travel cost, completing the circuit is impossible. Otherwise, a valid start must exist. Traverse the array once while maintaining two values: totalTank (overall gas minus cost) and currTank (fuel since the current candidate start). When currTank becomes negative at station i, any station between the current start and i cannot be a valid start. Reset the candidate start to i + 1 and reset currTank to zero. Continue scanning until the end of the array. If totalTank >= 0, the final candidate start index is guaranteed to complete the circuit. This greedy reasoning avoids rechecking failed segments and runs in linear time.
This technique works because once a deficit occurs, the accumulated shortage cannot be compensated by any station inside the failed segment. Skipping directly to the next index eliminates redundant checks. The algorithm operates entirely on the input arrays, making it both time and space efficient. The problem is a classic example of reasoning with cumulative balance in array traversal and applying a greedy decision rule.
Recommended for interviews: The greedy O(n) solution is the expected answer. Interviewers want to see the insight that eliminates unnecessary starting positions after a deficit. Mentioning the brute force simulation first shows you understand the problem mechanics, but deriving the greedy reset rule demonstrates stronger algorithmic reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n²) | O(1) | Useful for understanding the circular traversal logic or validating small inputs |
| Greedy Single Pass | O(n) | O(1) | Optimal approach for interviews and production due to linear scan and constant memory |