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] <= 104The Gas Station problem asks whether you can complete a full circular route of gas stations given two arrays: gas (fuel available at each station) and cost (fuel required to travel to the next station). The key insight is recognizing that if the total gas available across all stations is less than the total travel cost, completing the circuit is impossible.
A common greedy approach works by iterating through the stations while maintaining the current fuel balance. If the running balance becomes negative, it means the current starting point cannot complete the journey. At that point, the next station becomes the new candidate starting position, and the running balance resets. This works because any station between the failed start and the failure point cannot be a valid starting station.
By scanning the array once and tracking overall feasibility and candidate start points, we can determine the valid index efficiently. This strategy runs in linear time and uses constant extra space, making it optimal for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Single Pass | O(n) | O(1) |
take U forward
This approach leverages the greedy paradigm. The main idea is to iterate over the stations while keeping track of the total gas and total cost. Additionally, we maintain a running sum (which is the cumulative balance of gas at each station) and a start index. If the running sum ever becomes negative, it implies that the current segment of the journey is infeasible. Thus, we reset the running sum and choose the next station as the candidate for the starting point. Finally, if the total gas is greater than or equal to the total cost, the last chosen candidate is the valid starting point.
Time Complexity: O(n), where n is the number of stations.
Space Complexity: O(1), as extra space used is constant.
1#include <stdio.h>
2
3int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
4 int totalGas =
The function canCompleteCircuit iterates over the gas stations. It calculates the totalGas and totalCost along the way. While computing the running balance currentGas, if it becomes negative, the potential start index is updated to the next station. After the loop, if totalGas is greater than or equal to totalCost, it returns the last updated starting index; otherwise, it returns -1.
This approach attempts to simulate the journey starting from each station. For each potential start, check if the car can complete the circuit using the available gas at each station. While this approach may be easier to understand, it is inefficient because it checks each station iteratively, leading to potentially high computational costs for longer arrays. It is not recommended for larger datasets but can be useful for understanding how the journey works preliminarily.
Time Complexity: O(n^2) due to double iteration.
Space Complexity: O(1) as no extra space is utilized.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The optimal approach uses a greedy strategy. By tracking the total gas surplus and resetting the starting point whenever the running balance becomes negative, we can identify the correct starting station in a single pass.
If starting from station A causes the fuel balance to drop below zero at station B, then none of the stations between A and B can be valid starting points. This observation allows the algorithm to skip those stations and move the candidate start forward efficiently.
Yes, Gas Station is a well-known greedy problem frequently discussed in coding interviews at major tech companies. It tests a candidate’s ability to identify patterns and reason about optimal starting points in circular traversal problems.
The problem mainly relies on arrays since the input is given as gas and cost arrays. No additional complex data structures are required because the greedy solution only tracks running sums and indices.
JavaScript implements a naive approach to test each gas station as a potential starting point. The nested loop verifies the possibility to complete the full circuit from each start, breaking early when the journey fails.