# Zero Array Transformation III
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/zero-array-transformation-iii)
Canonical: https://scaleengineer.com/dsa/problems/zero-array-transformation-iii
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
---
## Problem
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
## Approach 1: Max-Flow on Explicit Graph
This approach models the problem as finding a maximum flow in a specially constructed graph. The core idea is that removing a query is a choice, and this choice has consequences for all array indices covered by that query. The constraints on how many queries can be removed are modeled as capacity constraints in the flow network.
**Time:** O(V^2 * E) with Dinic's algorithm, where V = O(n+q) and E = O(n*q). This is far too slow for the given constraints. · **Space:** O(n * q), to store the graph edges. For n, q up to 10^5, this is too large.
**Pros:** The approach is a direct and standard application of network flow, which is a well-understood paradigm.; It correctly models all constraints of the problem.
**Cons:** The time and space complexity are prohibitively high for the given constraints due to the large number of edges.
### Explanation
First, we determine if a solution is even possible. For each index `i`, the total number of queries covering it must be at least `nums[i]`. We can calculate the `total_coverage[i]` for all `i` efficiently using a difference array. Then, we compute the surplus `d[i] = total_coverage[i] - nums[i]`. If any `d[i]` is negative, we return -1.

Next, we build a flow network. We create a source `S`, a sink `T`, a node for each query, and a node for each array index. 

*   Edges from `S` to each query node have a capacity of 1, meaning we can choose to remove each query at most once.
*   Edges from each index node `v_i` to `T` have a capacity of `d[i]`, enforcing the surplus constraint at that index.
*   Edges from a query node `u_j` to an index node `v_i` exist if query `j` covers index `i`. These have infinite capacity to propagate the 'removal' effect.

The maximum flow from `S` to `T` gives the maximum number of queries we can remove. We can use an algorithm like Dinic's to find this value.

```java
// Conceptual code for the explicit graph max-flow approach
// A full max-flow solver implementation is required.

public int solveWithExplicitMaxFlow(int[] nums, int[][] queries) {
    int n = nums.length;
    int q = queries.length;

    // 1. Calculate d[i] (surplus coverage)
    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;
        }
    }

    // 2. Build graph and run max-flow
    int source = 0, sink = n + q + 1;
    MaxFlowSolver solver = new MaxFlowSolver(n + q + 2);

    for (int j = 0; j < q; j++) {
        solver.addEdge(source, j + 1, 1); // S to query node u_j
        int l = queries[j][0], r = queries[j][1];
        for (int i = l; i <= r; i++) {
            // query node u_j to index node v_i
            solver.addEdge(j + 1, q + i + 1, Integer.MAX_VALUE);
        }
    }

    for (int i = 0; i < n; i++) {
        // index node v_i to Sink
        solver.addEdge(q + i + 1, sink, (int)d[i]);
    }

    return solver.getMaxFlow(source, sink);
}
```
### Algorithm
*   **Surplus Calculation**: First, for each index `i`, calculate the surplus coverage `d[i] = (number of queries covering i) - nums[i]`. This can be done in `O(n+q)` time using a difference array. If any `d[i]` is negative, it's impossible to zero out the array, so return -1.
*   **Flow Network Construction**: Model the problem as a maximum flow problem. Construct a flow network with:
    *   A source node `S` and a sink node `T`.
    *   A node `u_j` for each query `j`. Add a directed edge from `S` to `u_j` with capacity 1. This represents the choice of whether to remove query `j`.
    *   A node `v_i` for each index `i`. Add a directed edge from `v_i` to `T` with capacity `d[i]`. This represents the maximum number of covering queries that can be removed for index `i`.
    *   For each query `j` with range `[l, r]`, and for every index `i` in `[l, r]`, add a directed edge from `u_j` to `v_i` with infinite capacity. This signifies that if query `j` is removed, it impacts all indices it covers.
*   **Max-Flow Calculation**: The maximum flow from `S` to `T` in this network corresponds to the maximum number of queries that can be removed. A flow of 1 from `S` through `u_j` means we 'select' query `j` for removal. The flow is constrained by the capacities `d[i]` at each index node.
*   **Algorithm**: Use a standard max-flow algorithm like Dinic's or Edmonds-Karp to compute the maximum flow. The resulting flow value is the answer.

## Approach 2: Max-Flow with Segment Tree Optimization
This approach improves upon the naive max-flow model by optimizing the graph structure. A segment tree is used to represent the connections between queries and the indices they cover, drastically reducing the number of edges in the graph.
**Time:** O(V^2 * E) = O((n+q)^2 * q log n). This is an improvement but still not fast enough. · **Space:** O(q log n + n) to store the optimized graph.
**Pros:** Significantly reduces the size of the graph compared to the naive approach.; Correctly solves the problem.
**Cons:** While more efficient than the naive max-flow, the time complexity is still too high for the given constraints.; The implementation is significantly more complex due to the segment tree integration within the flow network.
### Explanation
The fundamental idea remains the same as the explicit graph approach: model the problem as a max-flow problem. However, we address the performance bottleneck caused by the `O(n*q)` edges. A query `[l, r]` needs to be connected to all index nodes from `l` to `r`. This 'range connection' can be efficiently represented using a segment tree.

The graph construction is modified as follows: we introduce a layer of `O(n)` segment tree nodes. A query node `u_j` for `[l,r]` is connected to `O(log n)` segment tree nodes that represent the interval `[l,r]`. The flow then travels down the segment tree hierarchy to the leaf nodes, which in turn are connected to the actual index nodes `v_i`. This reduces the number of edges from `O(n*q)` to `O(q log n)`, making the graph much sparser.

Even with this optimization, running a standard max-flow algorithm like Dinic's on the resulting graph is generally still too slow given that `n` and `q` can be up to 10^5.

```java
// Conceptual code for the segment tree optimized max-flow
// This requires a MaxFlowSolver and a Segment Tree structure integrated.

public int solveWithSegTreeMaxFlow(int[] nums, int[][] queries) {
    // ... calculate d[i] as before ...

    // Total vertices: S, T, q queries, n indices, O(4n) for seg tree
    int numVertices = 2 + q + n + 4 * n;
    MaxFlowSolver solver = new MaxFlowSolver(numVertices);
    // ... map nodes to integer IDs ...

    // Add S -> u_j and v_i -> T edges as before

    // Build segment tree structure with flow edges
    // 1. Edges from parent segment tree nodes to children (infinite capacity)
    // 2. Edges from leaf segment tree nodes to index nodes v_i (infinite capacity)

    // Add edges from query nodes to segment tree
    for (int j = 0; j < q; j++) {
        int l = queries[j][0], r = queries[j][1];
        // Decompose [l,r] into O(log n) segment tree nodes
        // For each segment tree node st_k in the decomposition:
        //   solver.addEdge(u_j, st_k, Integer.MAX_VALUE);
    }

    return solver.getMaxFlow(source, sink);
}
```
### Algorithm
*   **Surplus Calculation**: Same as the previous approach, calculate `d[i]` and return -1 if any `d[i] < 0`.
*   **Optimized Flow Network**: The key bottleneck is the `O(n*q)` edges from query nodes to index nodes. We can reduce this by introducing a segment tree over the indices `0, ..., n-1`.
    *   The network still has a source `S`, sink `T`, query nodes `u_j`, and index nodes `v_i`.
    *   Edges `S -> u_j` (cap 1) and `v_i -> T` (cap `d[i]`) are the same.
    *   We add `O(n)` nodes representing the intervals in the segment tree.
    *   For each query `j=[l,r]`, instead of adding edges to all `v_i` in `[l,r]`, we add `O(log n)` edges from `u_j` to the segment tree nodes that cover the interval `[l,r]`.
    *   Flow propagates down the segment tree from parent nodes to child nodes via infinite capacity edges.
    *   Finally, leaf nodes of the segment tree (representing single indices) are connected to their corresponding index nodes `v_i` with infinite capacity edges.
*   **Max-Flow Calculation**: Run a max-flow algorithm on this more compact graph. The number of vertices is `O(n+q)` and the number of edges is `O(q log n + n)`.

## Approach 3: Greedy Algorithm on the Dual Problem
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.
**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.
**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.
### Explanation
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.

```java
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);
    }
}
```
### 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.

# Solutions
### Java

```java
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();
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxRemoval(vector<int> &nums, vector<vector<int>> &queries) {
    sort(queries.begin(), queries.end());
    priority_queue<int> pq;
    int n = nums.size();
    vector<int> d(n + 1, 0);
    int s = 0, j = 0;
    for (int i = 0; i < n; ++i) {
      s += d[i];
      while (j < queries.size() && queries[j][0] <= i) {
        pq.push(queries[j][1]);
        ++j;
      }
      while (s < nums[i] && !pq.empty() && pq.top() >= i) {
        ++s;
        int end = pq.top();
        pq.pop();
        --d[end + 1];
      }
      if (s < nums[i]) {
        return -1;
      }
    }
    return pq.size();
  }
};

```

### Python

```python
class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int: queries . sort() pq = [] d = [0] * (len(nums) + 1) s = j = 0 for i, x in enumerate(nums): s += d[i] while j < len(queries) and queries[j][0] <= i: heappush(pq, - queries[j][1]) j += 1 while s < x and pq and - pq[0] >= i: s += 1 d[- heappop(pq) + 1] -= 1 if s < x: return - 1 return len(pq)

```