3362: Zero-Array-Transformation-III
Medium

table of contents

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