Show problems as
Classic problem #3356MediumArrayTwo PointersBinary SearchPrefix Sum

Zero Array Transformation II

Real-world version: Earliest Schedule Prefix That Empties Every Tank
Tracked in this browser only
Read Zero Array Transformation II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def earliest_prefix(levels: list[int], windows: list[list[int]]) -> int:
Java
public int earliestPrefix(int[] levels, int[][] windows)

More on the same topics