Gas Station
Medium
0 views
Topics:
ArraysGreedy Algorithms
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] <= 104- The input is generated such that the answer is unique.
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What are the constraints on the size of the `gas` and `cost` arrays? Should I assume they are always the same size?
- Can the values in the `gas` and `cost` arrays be negative, zero, or only positive integers?
- If multiple starting gas stations allow a complete circuit, which one should I return (e.g., the smallest index)?
- Is it possible for the total gas available to be less than the total cost required to complete the circuit?
- Is it guaranteed that the `gas` and `cost` arrays are valid (e.g., not null or empty)?
Brute Force Solution
Approach
The core idea is to try starting at every single gas station. We want to simulate a trip around the entire track for each starting point to see if it's possible to complete the circuit. This exhaustive check guarantees we find a solution if one exists.
Here's how the algorithm would work step-by-step:
- First, pick a gas station to start from.
- Pretend to start your journey at that gas station.
- Simulate driving to the next gas station. Check if you have enough gas to get there.
- If you don't have enough gas, this starting point won't work. Move on to the next gas station as a potential starting point.
- If you do have enough gas, add the gas you get at the next station and continue to the next station, repeating the gas check.
- Keep going around the track, station by station, adding gas and using gas until you arrive back at your starting station.
- If you successfully complete the entire circuit, you've found a valid starting station. If not, try the next station as the starting point and repeat the process.
- If you've tried every gas station as a starting point and none of them work, then there's no solution.
Code Implementation
def can_complete_circuit_brute_force(gas, cost):
number_of_stations = len(gas)
for starting_station in range(number_of_stations):
current_gas = 0
possible = True
current_station = starting_station
# Simulate the trip around the track
for _ in range(number_of_stations):
current_gas += gas[current_station]
current_gas -= cost[current_station]
if current_gas < 0:
possible = False
break
current_station = (current_station + 1) % number_of_stations
# If we made it all the way around, return start
if possible:
return starting_station
# If no starting station works, return -1
return -1
Big(O) Analysis
Time Complexity
O(n²) – The algorithm iterates through each gas station as a potential starting point, which takes O(n) time. For each starting station, the algorithm simulates a complete circuit around all n gas stations to check if it's a valid starting point. Therefore, in the worst case, we perform a complete circuit check for each of the n possible starting points. This results in nested loops, where the outer loop iterates through the starting stations and the inner loop simulates the circuit. The total number of operations is proportional to n * n, which simplifies to O(n²).
Space Complexity
O(1) – The described solution simulates the gas station trip using a fixed number of variables to track the current gas amount and the starting station index. No auxiliary data structures that scale with the input size (N, the number of gas stations) are used. Therefore, the algorithm's space complexity is constant, independent of the input size.
Optimal Solution
Approach
The problem can be solved efficiently by recognizing that if a solution exists, it must start at some gas station. We can find this starting station by iteratively tracking the accumulated fuel and identifying when it becomes negative, indicating a bad starting point.
Here's how the algorithm would work step-by-step:
- First, check if it's even possible to complete the circuit. Calculate the total gas and the total cost. If the total gas is less than the total cost, there's no solution.
- Start at the first gas station and keep track of your current fuel as you 'drive' around the circuit.
- At each gas station, add the gas you get and subtract the cost to reach the next station.
- If your fuel ever drops below zero, that means the current starting station is not a good one. In this case, reset your current fuel to zero and move the starting station to the next station after the point where the fuel went negative.
- Continue this process until you've either found a valid starting station or have checked all possible starting stations.
- If a valid starting station is found (meaning you've made it all the way around the circuit without your fuel ever dropping below zero), return that starting station's index. If you've checked all stations and none work, then there is no solution.
Code Implementation
def can_complete_circuit(gas, cost):
total_gas = sum(gas)
total_cost = sum(cost)
# If total gas is less than total cost, impossible to complete.
if total_gas < total_cost:
return -1
current_fuel = 0
starting_station = 0
for i in range(len(gas)):
current_fuel += gas[i] - cost[i]
# If fuel drops below zero, this starting point is invalid.
if current_fuel < 0:
starting_station = i + 1
current_fuel = 0
#If a valid starting station is found, return it.
return starting_station
Big(O) Analysis
Time Complexity
O(n) – The algorithm iterates through the gas stations array (of size n) to calculate the total gas and total cost, which takes O(n) time. Then, it iterates through the gas stations again, maintaining a current fuel level and a potential starting station. If the fuel drops below zero, the starting station is advanced. Although the inner process advances the starting point, it still only examines each station a constant number of times across the whole process. Therefore, the primary loop dominates, resulting in a linear time complexity of O(n).
Space Complexity
O(1) – The algorithm uses a constant amount of extra space. It only stores a few integer variables: the total gas, the total cost, the current fuel, and the starting station index. The space required does not depend on the number of gas stations (N), so the auxiliary space complexity is constant.
Edge Cases
| Case | How to Handle |
|---|---|
| gas or cost is null | Return -1 immediately as the input is invalid. |
| gas or cost is empty | Return -1 immediately as no stations are available. |
| gas and cost have different lengths | Return -1 immediately since gas needed at station i can't be evaluated. |
| Only one gas station and cost is higher than gas | Return -1 as the car cannot reach the first station itself. |
| Only one gas station and cost is lower than or equal to gas | Return 0 since the car can start and complete the circuit at the first station. |
| Total gas is less than total cost | Return -1 as it is impossible to complete the entire circuit. |
| Integer overflow possibility due to large gas/cost values | Use long data type to avoid overflow during cumulative calculations of gas and cost. |
| All gas values are 0, and some cost values are non-zero | The algorithm should correctly identify that no starting point will lead to a completed circuit and return -1. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
