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.length
1 <= n <= 105
0 <= gas[i], cost[i] <= 104
This problem asks to find a gas station to start a circular route, given the amount of gas at each station (gas
) and the cost to travel to the next station (cost
). We need to determine if a complete circuit is possible, and if so, return the starting index; otherwise, return -1.
The solution employs a greedy approach with two pointers (i
and j
). The core idea is to keep track of the remaining fuel (s
) while iterating through the stations. If at any point the remaining fuel becomes negative, it means the current starting point (i
) is invalid, and we need to move the starting point (i
) backwards and adjust the fuel accordingly.
Algorithm:
Initialization:
i
and j
are initialized to n - 1
(the last station index), where n
is the number of gas stations.s
(sum) keeps track of the remaining fuel, initialized to 0.cnt
counts the number of stations visited.Iteration:
while
loop continues until all stations have been considered (cnt < n
).s
is updated by adding the gas at station j
and subtracting the cost to travel to the next station.cnt
is incremented.j
moves to the next station (circularly using the modulo operator %
).while
loop handles cases where s
becomes negative. This indicates that the current starting point (i
) is infeasible. The loop moves i
backwards, adjusts s
by adding the gas and subtracting the cost at the new starting point (i
), and increments cnt
.Result:
cnt >= n
), s
is still less than 0, it means no valid starting point exists, so -1 is returned.i
represents the index of a valid starting point, which is returned.Time Complexity Analysis:
The outer while
loop iterates at most n
times (number of gas stations). The inner while
loop also iterates at most n
times in the worst case (when every starting point is invalid). Therefore, the total time complexity is O(n) in the worst-case scenario, but it could be much less if a solution is found early.
Space Complexity Analysis:
The solution uses a constant amount of extra space for variables (i
, j
, s
, cnt
). Therefore, the space complexity is O(1), which is constant.
Example Walkthrough (Example 1):
gas
= [1,2,3,4,5], cost
= [3,4,5,1,2]
i = j = 4
, s = 0
, cnt = 0
s = 5 - 2 = 3
, cnt = 1
, j = 0
s = 3 + 1 - 3 = 1
, cnt = 2
, j = 1
s = 1 + 2 - 4 = -1
, cnt = 3
, j = 2
(s becomes negative)i = 3
, s = -1 + 4 - 5 = -2
, cnt = 4
(still negative)i = 2
, s = -2 + 3 - 5 = -4
, cnt = 5
(still negative)i = 1
, s = -4 + 2 - 4 = -6
, cnt = 6
(still negative)i = 0
, s = -6 + 1 - 3 = -8
, cnt = 7
(still negative)