N gas stations along a circular route, where the amount of gas at station i is
arr[i]. You have a car with an unlimited gas tank and it costs
cost[i] of gas to travel from station
i to its next station (
i+1). At the beginning of the journey, the tank is empty at one of the gas stations. Write a program to return the minimum starting gas station’s index so that you can travel around the circuit once, otherwise return -1
- Completing the circuit means starting at
iand ending up at
- If there exists a solution, it is guaranteed to be unique.
- Both input arrays are non-empty and have the same length.
- Each element in the input arrays is a non-negative integer.
Input: arr = [11,12,13,14,15] cost = [6,8,10,2,4] Output: 3 Explanation: Begin at station 3 (index 3) and fill up with 14 unit of gas. Gas available in Tank = 0 + 14 = 14 Travel to station 4. Gas available in tank = 14 - 2 + 15 = 27 Travel to station 0. Gas available in tank = 27 - 2 + 1 = 27 Travel to station 1. Gas available in tank = 27 - 6 + 2 = 23 Travel to station 2. Gas available in tank = 23 - 8 + 3 = 18 Travel to station 3. The cost is 10.Your gas is enough to travel back to station 3.Therefore, return 3 as the starting index.
Input: arr = [2,3,4] cost = [3,4,3] Output: -1 Explanation: You can't start at station 0 or 1, as there is not enough gas to travel to the next station. Let's start at station 2 and fill up with 4 unit of gas. Gas available in tank = 0 + 4 = 4 Travel to station 0. Gas available in tank = 4 - 3 + 2 = 3 Travel to station 1. Gas available in tank = 3 - 3 + 3 = 3 You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.Therefore, you can't travel around the circuit once no matter where you start.