Scale Engineer

Zero Array Transformation III

Med
#2987Time: O((n+q)log(n+q)). `O(n+q)` for setup, `O(q log q)` for sorting, `O(n log n)` to build the segment tree, and `O(q log n)` to process queries.Space: O(n) for the `d` array, the Fenwick tree, and the segment tree.
Patterns
GreedyPrefix Sum
Algorithms
Sorting
Data structures
ArrayHeap (Priority Queue)

Prompt

You are given an integer array nums of length n and a 2D array queries where queries[i] = [li, ri].

Each queries[i] represents the following action on nums:

  • Decrement the value at each index in the range [li, ri] in nums by at most 1.
  • The amount by which the value is decremented can be chosen independently for each index.

A Zero Array is an array with all its elements equal to 0.

Return the maximum number of elements that can be removed from queries, such that nums can still be converted to a zero array using the remaining queries. If it is not possible to convert nums to a zero array, return -1.

 

Example 1:

Input: nums = [2,0,2], queries = [[0,2],[0,2],[1,1]]

Output: 1

Explanation:

After removing queries[2], nums can still be converted to a zero array.

  • Using queries[0], decrement nums[0] and nums[2] by 1 and nums[1] by 0.
  • Using queries[1], decrement nums[0] and nums[2] by 1 and nums[1] by 0.

Example 2:

Input: nums = [1,1,1,1], queries = [[1,3],[0,2],[1,3],[1,2]]

Output: 2

Explanation:

We can remove queries[2] and queries[3].

Example 3:

Input: nums = [1,2,3,4], queries = [[0,3]]

Output: -1

Explanation:

nums cannot be converted to a zero array even after using all the queries.

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 0 <= li <= ri < nums.length

Approaches

3 approaches with complexity analysis and trade-offs.

This highly efficient approach reframes the problem using linear programming duality. The original problem of maximizing removed queries is transformed into a dual problem of minimizing a certain cost. This dual problem has a special structure that allows it to be solved optimally with a greedy algorithm, which is much faster than general-purpose max-flow or LP solvers.

Algorithm

  • Surplus Calculation: As in other approaches, compute d[i] = total_coverage[i] - nums[i]. If any d[i] < 0, return -1.
  • LP Duality: The problem can be formulated as a 0-1 integer program. By the principles of LP duality, this primal problem is equivalent to a dual LP: minimize sum(d[i] * y_i) subject to sum_{k=l_j to r_j} y_k >= 1 for each query j, and y_i >= 0. The optimal value of this dual problem is our answer.
  • Greedy Algorithm: This specific type of dual LP can be solved optimally using a greedy algorithm. The strategy is to process queries in a specific order and satisfy their constraints using the 'cheapest' resources available.
    1. Sort all queries by their right endpoint r_j in ascending order.
    2. Initialize an array y of size n to all zeros. We use a Fenwick tree (BIT) to maintain y to support fast range sums and point updates.
    3. Build a segment tree over the d array to efficiently find the index i with the minimum d[i] within any range [l, r]. To handle ties, we store pairs (d[i], i) and prioritize the one with the larger index i.
    4. Iterate through the sorted queries [l, r]. For each query: a. Use the Fenwick tree to find the current sum S = sum_{k=l to r} y_k. b. If S < 1, the constraint for this query is not met. We need to increase the sum by needed = 1 - S. c. To do this with minimum cost, use the d-segment tree to find the index i* in [l, r] with the minimum d[i*] (tie-breaking with largest i*). d. Increase y[i*] by needed. This is done by updating the Fenwick tree at i*. The total cost increases by needed * d[i*].
  • Result: The accumulated total cost is the answer. Since y_i can be fractional, the cost is a double. The final answer is this cost rounded to the nearest integer.

Walkthrough

This method is the most optimal. After calculating the surplus array d, we solve the dual of the problem's LP formulation. The greedy strategy works as follows:

We sort the queries by their right endpoint. This order is crucial. We iterate through the sorted queries. For each query [l, r], we check if its corresponding dual constraint (sum of y_k >= 1) is satisfied. The y_k values represent a sort of 'dual price' we assign to each index. We can efficiently check the sum using a Fenwick tree.

If the constraint is not met, we need to increase the y values for indices in [l, r]. To minimize the total cost (sum d[i]y[i]), we should put the required increase onto the y_k where d[k] is smallest. To find this cheapest index k in the range [l, r] efficiently, we use a segment tree built on the d array. In case of ties in d values, we pick the rightmost index, as this has the best chance of helping satisfy constraints for subsequent queries (which are sorted by right endpoint).

We update the chosen y[k] in our Fenwick tree and add the cost incurred to our total. After processing all queries, the total accumulated cost gives the maximum number of queries we can remove.

class Solution {    // Requires a Segment Tree for Range Minimum Query on d, returning a pair {value, index}.    // Requires a Fenwick Tree for range sum/point update on y (using doubles).     public int solve(int[] nums, int[][] queries) {        int n = nums.length;        long[] coverage = new long[n + 1];        for (int[] query : queries) {            coverage[query[0]]++;            if (query[1] + 1 <= n) {                coverage[query[1] + 1]--;            }        }         long[] d = new long[n];        long currentCoverage = 0;        for (int i = 0; i < n; i++) {            currentCoverage += coverage[i];            d[i] = currentCoverage - nums[i];            if (d[i] < 0) return -1;        }         Arrays.sort(queries, (a, b) -> Integer.compare(a[1], b[1]));         SegTree dSegTree = new SegTree(d); // For finding min d[i] in a range        FenwickTree yFenwickTree = new FenwickTree(n); // For y_i values                double totalCost = 0.0;         for (int[] query : queries) {            int l = query[0], r = query[1];            double currentSum = yFenwickTree.query(l, r);                        if (currentSum < 1.0 - 1e-9) { // Use tolerance for float comparison                double needed = 1.0 - currentSum;                Pair<Long, Integer> best = dSegTree.query(l, r); // find {min_d, index}                int bestIndex = best.getValue();                long costOfIndex = best.getKey();                                yFenwickTree.update(bestIndex, needed);                totalCost += needed * costOfIndex;            }        }        return (int) Math.round(totalCost);    }}

Complexity

Time

O((n+q)log(n+q)). `O(n+q)` for setup, `O(q log q)` for sorting, `O(n log n)` to build the segment tree, and `O(q log n)` to process queries.

Space

O(n) for the `d` array, the Fenwick tree, and the segment tree.

Trade-offs

Pros

  • This is the most efficient approach with a polynomial time complexity that is well within the limits.

  • It provides an exact, optimal solution.

Cons

  • The underlying theory (LP duality) is non-trivial and may not be immediately obvious.

  • Requires implementation of two advanced data structures: a Fenwick tree and a segment tree.

  • Involves floating-point arithmetic, which requires careful handling.

Solutions

class Solution {public  int maxRemoval(int[] nums, int[][] queries) {    Arrays.sort(queries, (a, b)->Integer.compare(a[0], b[0]));    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->b - a);    int n = nums.length;    int[] d = new int[n + 1];    int s = 0, j = 0;    for (int i = 0; i < n; i++) {      s += d[i];      while (j < queries.length && queries[j][0] <= i) {        pq.offer(queries[j][1]);        j++;      }      while (s < nums[i] && !pq.isEmpty() && pq.peek() >= i) {        s++;        d[pq.poll() + 1]--;      }      if (s < nums[i]) {        return -1;      }    }    return pq.size();  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem