Courier Loop Start
MediumGreedy
Problem
A delivery scooter runs a circular route through n depots numbered 0 to n - 1. At depot i it can charge charge[i] units of battery, and driving from depot i to depot (i + 1) % n uses drain[i] units. The battery has no upper limit.
The scooter starts at some depot with an empty battery, charges there, and must drive the full loop back to its starting depot without the battery ever going negative. Return the smallest starting depot that works, or -1 if none does.
Example 1
- Input:
- charge = [1, 2, 3, 4, 5], drain = [3, 4, 5, 1, 2]
- Output:
- 3
From depot 3: 4−1 = 3, +5−2 = 6, +1−3 = 4, +2−4 = 2, +3−5 = 0. Battery never goes negative.
Example 2
- Input:
- charge = [2, 3, 4], drain = [3, 4, 3]
- Output:
- -1
Total charge 9 is less than total drain 10, so no start can work.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ charge[i], drain[i] ≤ 10^5
Hint
Show the first hint
If the total charge is less than the total drain, can any start work? And if it is at least as large?
Walkthrough
How to approach it
01Clarify before coding
- Is the battery unlimited? Yes, there is no cap.
- May several starts work? Yes (e.g. all zeros); return the smallest index.
- Does a battery of exactly 0 on arrival count as OK? Yes, only negative is a failure.
02Brute force
Simulate the full loop from every possible start.
Cost: O(n²), 10^10 steps at n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.