First circular tour that visits all petrol pumps
Problem
Petrol pumps sit on a circular road. Pump i gives petrol[i] litres, and reaching the next pump costs distance[i] litres. Starting with an empty tank, return the first pump index from which you can complete the whole circle, or −1 if none works.
Example 1
Input: petrol = [4, 6, 7, 4], distance = [6, 5, 3, 5] Output: 1
Also asked as: Find the first circular tour that visits all Petrol Pumps
Test cases
Case 1
Input: [[4,6],[6,5],[7,3],[4,5]] Expected: 1
Case 2
Input: [[6,4],[3,6],[7,3]] Expected: 2
Case 3
Input: [[1,2],[2,3]] Expected: -1
View solutionHide solution1 approach
1. Single pass — reset start on deficit
Time O(n)Space O(1)
Track a running tank. If it ever goes negative, no start up to here works; set start to the next pump and reset the tank. Feasible overall iff total petrol ≥ total distance.
function firstTour(pumps) { // pumps[i] = [petrol, distance] let start = 0, tank = 0, total = 0; for (let i = 0; i < pumps.length; i++) { const diff = pumps[i][0] - pumps[i][1]; tank += diff; total += diff; if (tank < 0) { start = i + 1; tank = 0; } } return total >= 0 ? start : -1;}