Gas Station Circuit
Updated
Problem statement
There are n gas stations on a circular route. Station i provides gas[i] units of gas, and traveling clockwise from station i to station (i + 1) % n costs cost[i] units.
Your car has an unlimited tank and starts with an empty tank at a station of your choice. Collect the gas at each station before paying to travel to the next station. The tank must never become negative.
Return the smallest zero-based starting index that lets you complete one full circuit clockwise. Return -1 if no starting station works.
Function
canCompleteCircuit(gas: int[], cost: int[]) → intExamples
Example 1
gas = [1,2,3,4,5]cost = [3,4,5,1,2]return = 3Starting at station 3, the tank after each move is 3,6,4,2,0. Starts 0, 1, and 2 fail, so 3 is the smallest valid index.
Example 2
gas = [2,3,4]cost = [3,4,3]return = -1The route supplies 9 gas units and needs 10, so a full circuit is impossible.
Example 3
gas = [1,1]cost = [1,1]return = 0Both stations work. The smallest starting index is 0.
Constraints
1 <= gas.length <= 100000.cost.length == gas.length.0 <= gas[i], cost[i] <= 10000.
More Angel One Phone Screen questions
Similar questions at other companies
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Jump GamePaytm · PHONE SCREENPaytm interview questions
- Maximum Number of Events That Can Be AttendedByteDance · PHONE SCREENByteDance interview questions
- Remove the Fewest Magic BeansThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- Aggressive CowsAmazon · PHONE SCREEN
- Minimum Cost for a Target WeightPace Stock Broking Services · PHONE SCREEN
- Defer Expenses to Preserve BalanceDRW · PHONE SCREENDRW interview questions
- Container With Most WaterEPAM · PHONE SCREENEPAM interview questions
- Task Scheduler with CooldownTeradata · PHONE SCREEN
- Minimum Operations to Make Every Array Element OneOtter.ai · PHONE SCREENOtter.ai interview questions