Implement the circularTourStartIndex method that returns a starting petrol pump index that can complete the circular tour.
The input contains two arrays, petrol and distance, along with their length size. Each index represents one petrol pump on a circular route.
petrol[i] is the fuel available at that pump, and distance[i] is the fuel required to travel from that pump to the next pump.
Your task is to return the starting index from which the full circular tour can be completed. If no such starting point exists, return -1.
Example 1
[4,6,7,4][6,5,3,5]41Example 2
[6,3,7][4,6,3]32Example 3
[1,2,3][4,5,6]3-1Use a greedy approach with a running tank.
If the total petrol is less than the total distance, completing the circle is impossible. Otherwise, scan the pumps and track the current fuel balance. If the balance becomes negative at index i, no pump from the current start to i can be a valid start, so choose i + 1 as the next possible start.
After one full scan, the selected start index is the answer.
Pseudocode:
function circularTourStartIndex(petrol, distance, size):
totalBalance = 0
currentBalance = 0
start = 0
for i from 0 to size - 1:
gain = petrol[i] - distance[i]
totalBalance = totalBalance + gain
currentBalance = currentBalance + gain
if currentBalance < 0:
start = i + 1
currentBalance = 0
if totalBalance < 0:
return -1
return start