Reservoir Fill Day
Medium · prefix sum
A reservoir collects rainwater. The list rain gives the litres that flow in on each day, in order: rain[0] on day 1, rain[1] on day 2, and so on. Some days are dry, so a value can be 0, but it is never negative. Nothing ever leaves the reservoir.
A water company asks several questions. Each entry of targets is an amount of water in litres, and the question is: on which day does the reservoir first hold at least that much? Day numbers start at 1, and the water that flows in on a day counts for that same day.
Return a list with one answer per target, in the same order as targets. If the reservoir never reaches a target, the answer for it is -1. The same target may appear more than once.
Examples
Example 1
Input: rain = [3, 0, 4, 1, 2], targets = [1, 4, 8, 10, 11]
Output: [1, 3, 4, 5, -1]
After each day the reservoir holds 3, 3, 7, 8 and 10 litres. It first holds at least 1 litre on day 1, at least 4 on day 3, at least 8 on day 4 and at least 10 on day 5. It never holds 11.
Example 2
Input: rain = [0, 0, 5], targets = [5, 1]
Output: [3, 3]
The first two days are dry, so both targets are first reached on day 3.
Constraints
- 1 <= len(rain) <= 10^5
- 0 <= rain[i] <= 10^4
- 1 <= len(targets) <= 10^5
- 1 <= targets[i] <= 10^9