Tap here to switch tabs
Problem
Submissions

Problem: Zero Array Transformation II

Zero Array Transformation II asks for the fewest initial range operations that can reduce every array element to zero using independent bounded decrements, or report impossibility.

Statement

You are given an integer array nums and a list of operations queries, where each operation queries[i] = [l_i, r_i, val_i].

For a fixed integer k, apply the first k operations in order. When applying an operation [l_i, r_i, val_i], you may choose for every index j in the range l_i to r_i an integer decrement d_j such that 0≤dj≤vali0 \leq d_j \leq val_i, and then update nums[j] = nums[j] - d_j.

After applying the first k operations, the array is called a zero array if every element is equal to 00.

Return the minimum k such that it is possible to make nums a zero array after applying the first k operations. If it is impossible for any k, return −1-1.

Note: In each operation, the decrement chosen at each index can be different, but it must be between 00 and val_i inclusive.

Constraints:

  • 1≤1 \leq nums.length ≤105\leq 10^5

  • 0≤0 \leq nums[i] ≤5⋅105\leq 5 \cdot 10^5

  • 1≤1 \leq queries.length ≤105\leq 10^5

  • queries[i].length =3= 3

  • 0≤0 \leq l_i ≤\leq r_i << nums.length

  • 1≤1 \leq val_i ≤5\leq 5

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Zero Array Transformation II

Zero Array Transformation II asks for the fewest initial range operations that can reduce every array element to zero using independent bounded decrements, or report impossibility.

Statement

You are given an integer array nums and a list of operations queries, where each operation queries[i] = [l_i, r_i, val_i].

For a fixed integer k, apply the first k operations in order. When applying an operation [l_i, r_i, val_i], you may choose for every index j in the range l_i to r_i an integer decrement d_j such that 0≤dj≤vali0 \leq d_j \leq val_i, and then update nums[j] = nums[j] - d_j.

After applying the first k operations, the array is called a zero array if every element is equal to 00.

Return the minimum k such that it is possible to make nums a zero array after applying the first k operations. If it is impossible for any k, return −1-1.

Note: In each operation, the decrement chosen at each index can be different, but it must be between 00 and val_i inclusive.

Constraints:

  • 1≤1 \leq nums.length ≤105\leq 10^5

  • 0≤0 \leq nums[i] ≤5⋅105\leq 5 \cdot 10^5

  • 1≤1 \leq queries.length ≤105\leq 10^5

  • queries[i].length =3= 3

  • 0≤0 \leq l_i ≤\leq r_i << nums.length

  • 1≤1 \leq val_i ≤5\leq 5