Gas Station
Updated
Problem statement
There are n gas stations on a circular road, numbered 0 to n - 1. From station i you drive forward to station i + 1, and from station n - 1 you drive back to station 0.
Station i lets you fill up gas[i] units of fuel. The drive from station i to the next station burns cost[i] units. Your car's tank has no size limit, and it is empty when you start.
Choose a starting station and drive forward around the whole circle until you reach the start again. At every station on the way, including the first, you fill up there and then drive to the next station. The trip fails if the fuel would drop below zero on any drive. Arriving at a station with exactly zero fuel is allowed.
Return the index of a starting station from which the trip succeeds. If several stations work, return the smallest index. If no station works, return -1.
Function
canCompleteCircuit(gas: int[], cost: int[]) → intExamples
Example 1
gas = [1,4,2,5]cost = [3,2,4,1]return = 1The net change at each station is gas[i] - cost[i]: -2, 2, -2, 4. Station 0 fails at once: it gives 1 unit but the first leg needs 3.
Start at station 1 with an empty tank. Fill up 4 and drive to station 2 using 2, leaving 2. Fill up 2 and drive to station 3 using 4, leaving 0. Fill up 5 and drive to station 0 using 1, leaving 4. Fill up 1 and drive back to station 1 using 3, leaving 2. The tank never drops below zero, so station 1 works.
Station 3 also works, but the answer is the smaller index, 1.
Example 2
gas = [3,1,2]cost = [2,3,2]return = -1The stations give 3 + 1 + 2 = 6 units in total, but one full trip uses 2 + 3 + 2 = 7 units. No starting station can finish, so the answer is -1.
Example 3
gas = [0,6,1,0]cost = [2,1,2,2]return = 1Stations 0 and 3 have no fuel, and station 2 gives 1 unit for a leg of 2, so all three fail on their first leg. From station 1 the tank holds 5 after the first leg, then 4, then 2, then 0 when it arrives back at station 1. Ending the trip with exactly zero fuel is allowed, so the answer is 1.
Constraints
1 <= n <= 10^5gas.length == cost.length == n0 <= gas[i], cost[i] <= 10^4
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Minimum Station Tracks for a Train ScheduleBNSF Railway · ONSITE INTERVIEWBNSF Railway interview questions
- Best Time to Buy and Sell Stock IIKotak Mahindra Bank · ONSITE INTERVIEWKotak Mahindra Bank interview questions
- Minimize Total Weight After HalvingAmazon · ONSITE INTERVIEW
- Gas StationeBay · ONSITE INTERVIEWeBay interview questions
- Make an Array Non-Decreasing With One ModificationGoogle · ONSITE INTERVIEWGoogle interview questions
- Wizard Scroll Allocation StrategyJane Street · ONSITE INTERVIEWJane Street interview questions
- Maximize Compatible Car RidersUber Freight · PHONE SCREEN · ONSITE INTERVIEWUber Freight interview questions
- Maximize Monsters DefeatedSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Maximize Workday EarningsCitadel · OA · PHONE SCREEN · ONSITE INTERVIEWCitadel interview questions