Gas Station Loop Start
Updated
Problem statement
There are n fuel stations on a circular road, numbered 0 to n - 1. Driving forward from station i takes you to station i + 1, and from station n - 1 back to station 0.
At station i you can pick up gas[i] units of fuel. Driving from station i to the next station uses cost[i] units. The tank has no size limit and starts empty.
You pick a starting station and drive forward for one full lap until you are back at the start. At every station on the way, including the first one, you pick up its fuel and then drive to the next station. The lap fails if the fuel in the tank would drop below zero on any leg. Arriving at a station with exactly zero fuel is fine.
Return the index of a starting station that completes the lap. If several stations work, return the smallest index. If no station works, return -1.
Function
findLoopStart(gas: int[], cost: int[]) → intExamples
Example 1
gas = [3,1,4,2]cost = [2,3,1,3]return = 2Start at station 2 with an empty tank. Pick up 4 and drive to station 3 using 1, leaving 3. Pick up 2 and drive to station 0 using 3, leaving 2. Pick up 3 and drive to station 1 using 2, leaving 3. Pick up 1 and drive back to station 2 using 3, leaving 1. The tank never goes below zero.
Stations 0, 1 and 3 fail. From station 0 the tank holds 1 after the first leg, then 1 + 1 - 3 = -1 on the second. Stations 1 and 3 fail on their first leg.
Example 2
gas = [1,2,3]cost = [2,3,2]return = -1The stations give 6 units in total, but one lap burns 7 units. No starting station can finish, so the answer is -1.
Example 3
gas = [2,0,2,0]cost = [1,1,1,1]return = 0From station 0 the tank holds 1, then 0, then 1, then 0 after each leg, so the lap finishes. Arriving with exactly zero fuel is allowed. Station 2 also works, but station 0 is the smaller index, so the answer is 0.
Constraints
1 <= n <= 10^5gas.length == cost.length == n0 <= gas[i], cost[i] <= 10^4
More Nutanix Online Assessment questions
- Good SubsequencesOA · Seen Jul 2026
- Min Cost to Connect All PointsOA · Seen Jun 2026
- Digit Changes for a Multiple of 9OA · Seen Aug 2025
- Number of Players (for MTS2)OA · Seen Oct 2024
- Work Schedules (for MTS2)OA · Seen Oct 2024
- Minimum Operations to Convert ArrayOA · Seen Apr 2024
- No Adjacent CharactersOA · Seen Apr 2024
- Build a BST From a ListOA · Seen Nov 2022
- Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022
- Maximum Value of the Last RobotOA · Seen Aug 2021
Similar questions at other companies
- Minimum Cost K-Capable ModelsMicrosoft · OAMicrosoft interview questions
- Optimal TransferSnowflake · OASnowflake interview questions
- Minimum Redistribution CostAmazon · OA
- Redistribute MegaseedsRubrik · OARubrik interview questions
- Maximum Distinct Items Within a BudgetAdobe · OAAdobe interview questions
- Minimum AmountBelvedere Trading · OA
- Focus on Efficiency (2024 NG)Google · OAGoogle interview questions
- Running Through Walls with Limited EnergyScale AI · OAScale AI interview questions
- Make the Array PositiveAtlassian · OAAtlassian interview questions
- Maximize Compatible Car RidersUber Freight · PHONE SCREEN · ONSITE INTERVIEWUber Freight interview questions