Gas Station Loop
Updated
Problem statement
There are n gas stations on a loop road, numbered 0 to n - 1 in driving order. After station n - 1 the road leads back to station 0.
- At station
iyou can addgas[i]units of gas to your tank. - Driving from station
ito the next station usescost[i]units of gas. - You can only make a drive if the tank holds at least its cost. Arriving with an empty tank is fine.
- The tank has no size limit, and it is empty when you start.
Return the index of a station where you can start and drive once around the whole loop, back to that station. If several stations work, return the smallest index. If no station works, return -1.
Function
findStartStation(gas: int[], cost: int[]) → intExamples
Example 1
gas = [2,5,1,4]cost = [3,2,4,2]return = 1Start at station 1 with an empty tank. Fill 5 and drive to station 2 using 2, so 3 is left. Fill 1 (now 4) and drive to station 3 using 4: you arrive with 0, which is allowed. Fill 4 and drive to station 0 using 2 (2 left), then fill 2 (now 4) and drive back to station 1 using 3. Station 0 does not work: you fill 2 but the first drive costs 3.
Example 2
gas = [3,1,2]cost = [2,3,2]return = -1In total the stations give 6 units of gas, but the full loop needs 7. No start can make up the missing unit, so the answer is -1.
Example 3
gas = [4,0,3,0]cost = [2,2,1,2]return = 0Starting at station 0 works: fill 4 and reach station 1 with 2 left, reach station 2 with 0 left, fill 3 and reach station 3 with 2 left, then reach station 0 with 0 left. Starting at station 2 also works. Stations 1 and 3 give no gas, so they cannot start. When several stations work, return the smallest index, which is 0.
Constraints
1 <= gas.length <= 2 * 10^4cost.length == gas.length0 <= gas[i], cost[i] <= 1000
More C3.ai interview questions
- Every Result of Grouping an ExpressionONSITE INTERVIEW · Seen Jan 2023
- Fewest Jumps to the Last IndexONSITE INTERVIEW · Seen Jan 2023
- Rotate a Square Grid ClockwiseONSITE INTERVIEW · Seen Jan 2023
- Movie Schedule for Maximum EnjoymentONSITE INTERVIEW · Seen Jan 2023
- Days Until a Warmer DayPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
- Can All Courses Be FinishedONSITE INTERVIEW · Seen Nov 2021
- Longest Arithmetic SubsequenceONSITE INTERVIEW · Seen Feb 2021
- Drop Recent Duplicate MessagesOA · Seen Oct 2026
- Maximum K-Star SumOA · Seen Oct 2026
- Fewest Turns to Open a Wheel LockPHONE SCREEN · Seen Nov 2024
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
- Capacity to Ship Packages Within DaysMicrosoft · OA · ONSITE INTERVIEWMicrosoft interview questions
- 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