0686MediumArrayTwo PointersBinary SearchPrefix Sum

Earliest Schedule Prefix That Empties Every Tank

Tracked in this browser only

Trains the technique from

LeetCode 3356Zero Array Transformation II

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A row of tanks is numbered from 0, and levels[i] is how many litres tank i currently holds. A maintenance schedule lists pump windows in the order they will run. Window j is windows[j] = [start, end, amount] and means: while that window is open, every tank numbered from start to end inclusive may be drained by any whole number of litres between 0 and amount, chosen separately for each tank. Tanks outside the window are untouched, and a tank can never go below 0.

Return the smallest k such that running only the first k windows of the schedule, in order, is enough to leave every tank empty. Return 0 if the tanks are already all empty, and -1 if running the whole schedule is not enough.

Examples

Example 1

Input: levels = [4, 0, 3], windows = [[0, 0, 3], [0, 2, 2], [2, 2, 5]]
Output: 3

With all three windows open, tank 0 can lose 3 litres in the first window and 1 in the second, tank 1 needs nothing, and tank 2 can lose 3 litres in the third window. Two windows leave tank 2 with a draw of only 2 against its 3 litres.

Example 2

Input: levels = [6], windows = [[0, 0, 2], [0, 0, 2]]
Output: -1

The single tank holds 6 litres and the whole schedule offers it a draw of only 2 plus 2, so it cannot be emptied.

Example 3

Input: levels = [0, 4], windows = [[0, 1, 2], [1, 1, 2]]
Output: 2

Tank 0 is already empty. Tank 1 holds 4 litres and is covered by both windows, whose amounts add up to exactly 4.

Constraints

1 <= levels.length <= 10^5
0 <= levels[i] <= 5 * 10^5
1 <= windows.length <= 10^5
windows[i].length == 3
0 <= windows[i][j] <= 10^5
Each window is [start, end, amount] with 0 <= start <= end < levels.length and 1 <= amount <= 5.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def earliest_prefix(levels: list[int], windows: list[list[int]]) -> int:

Java

public int earliestPrefix(int[] levels, int[][] windows)

The intended approach

Time O(n + q) for n tanks and q windows.Space O(n) for the delta array.

Since the litres drained from each tank are chosen independently, the first `k` windows suffice exactly when, for every tank, the amounts of the covering windows among those `k` add up to at least its level. Sweep the tanks from left to right holding the draw available at the current tank, and only open the next scheduled window when the current tank still falls short. A running array of deltas records where each opened window's contribution starts and where it expires, so the available draw is kept correct as the sweep moves on. Every window is opened at most once, so the cursor over the schedule never goes backwards.

Pythonentry point: earliest_prefix

def earliest_prefix(levels, windows):
    n = len(levels)
    decay = [0] * (n + 1)     # decay[i] is the change in available draw as we reach tank i
    available = 0
    used = 0
    for i in range(n):
        available += decay[i]
        # only open more windows when this tank still cannot be emptied
        while available < levels[i] and used < len(windows):
            start, end, amount = windows[used]
            used += 1
            if end < i:
                continue                       # that window is already behind us
            if start <= i:
                available += amount
            else:
                decay[start] += amount
            decay[end + 1] -= amount
        if available < levels[i]:
            return -1
    return used

The obvious version

Try every prefix length in turn. For a given length, add each window's amount into every tank it covers to get the total draw per tank, then check that no tank is left holding more than its draw. Return the first length that passes.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_earliest_prefix(levels, windows):
    n = len(levels)
    for k in range(len(windows) + 1):
        draw = [0] * n
        for w in range(k):
            start, end, amount = windows[w]
            for i in range(start, end + 1):
                draw[i] += amount
        if all(draw[i] >= levels[i] for i in range(n)):
            return k
    return -1

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in