3362: Zero-Array-Transformation-III
Medium

The intuition for this solution is to iterate through all elements in your array nums, and check greedily whether there are enough queries to convert the element to zero.

To be able to determine which queries might be useful, we can start by sorting queries from smallest to largest. Then, when we iterate through nums:

Code:

class Solution {
public:
    int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
        sort(queries.begin(), queries.end());
        priority_queue<int> pq;

        vector<int> difference (nums.size()+1, 0);
        int currentDifference = 0;

        for (int i = 0, j = 0; i < nums.size(); ++i) {
            currentDifference -= difference[i];
            while (j < queries.size() && i == queries[j][0]) {
                pq.push(queries[j++][1]);
            }
            while (currentDifference < nums[i] && !pq.empty() && pq.top() >= i) {
                ++currentDifference;
                ++difference[pq.top()+1];
                pq.pop();
            }
            if (currentDifference < nums[i]) {
                return -1;
            }
        }

        return (int)pq.size();
    }
};

Complexity: