First circular tour that visits all petrol pumps

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}