Zero Array Transformation III

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:

• at iteration i, we can also iterate through queries and add the end index of all the queries, with a starting index equal to i, to a max_heap, pq
  • since this algorithm is greedy, we are assuming all the previous indices are already valid, meaning to maximise value, we should be selecting queries with the largest coverage i.e. the largest end index
  • we thus add it to a max_heap so that we can always track the maximum end index
• we also need to keep track of the currDifference and make sure currDifference >= nums[i]
  • if it is NOT true, then we need to keep popping from the max_heap and adding to the currDifference if the ending index is greater than or equal to i
• we also maintain a difference array, difference, to make sure we keep track of when each query ends, and to subtract from currDifference once we reach the specified index

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

• Time: O(n + m log (m)) where n is the size of nums and m is the size of queries
• Space: O(n + m)