284. Find the First Circular Tour That Visits All Petrol Pumps

There are n petrol pumps arranged in a circle. Pump i has petrol[i] litres of fuel available, and dist[i] is the distance from pump i to the next pump (i+1, wrapping around to pump 0 after the last). Your truck starts with an empty tank and travels 1 litre per unit distance. Find the 0-indexed pump you should start at to complete the entire circular route without ever running out of fuel. It's guaranteed exactly one such starting pump exists (total petrol across all pumps is always >= total distance).

Input: The first line contains an integer n, the number of pumps. The second line contains n space-separated integers, petrol[i] at each pump. The third line contains n space-separated integers, dist[i] from each pump to the next. Output: Print a single integer - the 0-indexed pump to start from to complete the whole circular route.

1 <= n <= 10^5, 0 <= petrol[i], dist[i] <= 10^4

This greedy 'reset on negative balance' technique is a variant of the same underlying idea behind Kadane's-style running-sum algorithms - recognizing 'a running total that resets when it goes bad' as a broader reusable pattern connects this to several other array problems.

You're driving in a circle between fuel pumps, each giving you some fuel and costing some fuel to reach the next one. Find the ONE starting pump where you'd never run dry, guaranteed to complete the whole loop. Brute force: Try starting the full circular tour from every single pump individually, simulating the entire loop each time to check if fuel ever runs out - this costs O(n²) in the worst case, since each of the n candidate starts requires simulating up to n steps. Optimised: A single left-to-right pass suffices because of a clever guarantee: if starting at pump i fails at pump j (balance goes negative), then starting at ANY pump between i and j would ALSO fail by at least pump j (since it would have accumulated even less fuel by that point, having skipped i's contribution) - so you never need to re-try any pump between a failed candidate and its failure point, letting you safely jump your next candidate straight past the failure.

Walk through the pumps once, maintaining a running 'current surplus' (fuel gained minus distance spent since the last reset) and a separate running 'total surplus' across the whole route. Whenever the current surplus goes negative, it means no pump from the last reset point up to and including the current one could have been a valid start, so reset current surplus to 0 and set the candidate start to the next pump. Because the problem guarantees total petrol >= total distance, the last recorded candidate start is guaranteed to be the unique valid answer, and this is found without ever storing an auxiliary array, using only a couple of running totals. Time: O(n) Space: O(1)

For each of the n pumps, simulate starting there with an empty tank and driving the full circular route, tracking the fuel balance after each leg; if the balance ever goes negative, that starting pump fails, so move on to the next candidate. Since it's guaranteed a valid start exists, this eventually finds it, but simulating the entire route from scratch for every candidate start repeats a lot of the same arithmetic. Time: O(n^2) Space: O(1)

Compute the array of net fuel changes at each pump, diff[i] = petrol[i] - dist[i], then build its prefix-sum array over two copies of the array laid end to end (to handle wraparound) in a single O(n) pass. The correct starting pump is the index right after the position where this prefix sum reaches its overall minimum, since starting anywhere before that point would mean crossing the worst deficit with fuel already low. This computes the answer in one linear pass using an explicit auxiliary prefix-sum array, rather than the single running-total reset trick of the fully optimal approach. Time: O(n) Space: O(n)

1. Scan through the pumps left to right (conceptually extending around the circle), tracking a running fuel balance: add the current pump's fuel, subtract the distance to the next pump. 2. The moment this running balance goes negative at some pump, NONE of the pumps you've considered as a candidate start (from your current candidate up through this failing pump) could possibly be the answer. 3. Reset your candidate starting point to right after this failing pump, and reset the running balance back to 0, then keep scanning. 4. Because the problem guarantees a valid answer exists (total fuel is always at least total distance), whichever candidate you're STILL holding once the single scan finishes is guaranteed to be the correct answer.

Time: O(n) - a single pass through the pumps, with no repeated re-scanning of already-ruled-out candidates. Space: O(1) - just a running balance and a candidate index, regardless of how many pumps there are.

n = 1 (a single pump, trivially the answer since a valid start is guaranteed to exist); petrol[i] or dist[i] equal to 0 at some pump, both allowed by the constraints; n = 10^5 for performance.

Be ready to explain WHY skipping every pump between a failed candidate and its failure point is safe - this non-obvious guarantee is the entire reason the greedy single-pass approach works, and interviewers often ask you to justify it, not just apply it.