1/11
Loading...
🚚Snack Truck Start!
5 stalls on a circular street! Bars = each stall's refuel amount gain[i] Find a start so the tank never goes negative for one loop.
Loading...
5 stalls on a circular street! Bars = each stall's refuel amount gain[i] Find a start so the tank never goes negative for one loop.
A boss runs a midnight snack truck that delivers ingredients around a circular street lined with N stalls. At each stall i the truck is refueled by gain[i] liters, but driving to the next stall costs cost[i] liters. The fuel tank has unlimited capacity and starts empty. Find the index of the stall to start from so the truck can visit every stall exactly once clockwise and return to where it began. Return -1 if no such start exists. (If an answer exists, it is unique.)
gain = [2, 4, 1, 6, 3], cost = [4, 1, 5, 2, 2]
3
Per-stall diff (gain-cost) = [-2, +3, -4, +4, +1] Total = +2 ≥ 0, so an answer exists. Start at 3: tank goes 4 → 5 → 3 → 1 → 4, never negative — loop completed! Any other start dips below zero on the way.