223. Gas Station
Medium
Greedy Reset
Array
Problem
There are n gas stations arranged in a circle. gas[i] is the fuel available at station i and cost[i] is the fuel required to travel from station i to station i + 1. Return the starting station index from which the complete circuit can be traveled clockwise, or -1 if impossible.
Examples
Example 1
Input: [1,2,3,4,5], [3,4,5,1,2]
Output: 3
Example 2
Input: [2,3,4], [3,4,3]
Output: -1
Example 3
Input: [5], [4]
Output: 0
Constraints
� 1 <= gas.length == cost.length <= 100000
� 0 <= gas[i], cost[i] <= 10000
Hints
?? If total gas is less than total cost, no solution exists.
?? When the running tank becomes negative, the next station becomes the only possible new candidate.
Expected Complexity
Time: O(n)
Space: O(1)
Follow-up
Why can all stations between the previous candidate and failure point be skipped?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[1,2,3,4,5], [3,4,5,1,2]Expected
3