3355: Zero-Array-Transformation-I
Medium

I swear I have done this problem bef-

Instead of manually decrementing all the values between each query, realise that it is extremely inefficient, especially if we have multiple queries that are stacked on top of each other as we will be repeatedly iterating over the same values

In our case, the inefficiency we want to address is having to iterate over the same values multiple times. How should we make it so that we only have to do it once?

We can simply do this by initializing another array of the same size as nums called processedQueries and only incrementing the starting index of the query (processedQueries[starting_index]++;) and decrementing one past the ending index of the query (processedQueries[ending_index+1]--;).

This works, because as we iterate through processedQueries, we can treat incrementing the starting index as entering a query; as for all the values up until ending_index+1, they are all part of the same query. That is why we decrement one past the ending index, as all the future indices are not a part of the same query anymore.

This means we can keep track of the number of queries we have entered in O(1) time and calculate the maximum amount the value present at this index can be decremented by.

Therefore, if we cannot set any value present at any index to zero (by tracking the queries it is present in), it means we are unable to transform nums into a zero array and return false.

Else, if we have iterated through the entirety of nums with no issues, we can simply return true.

code

class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> processedQueries (nums.size()+1, 0);

        for (vector<int>& query : queries) {
            ++processedQueries[query[0]];
            --processedQueries[query[1]+1];
        }

        int decrementCounter = 0;
        for (int i = 0; i < nums.size(); ++i) {
            decrementCounter += processedQueries[i];
            if (decrementCounter < nums[i]) {
                return false;
            }
        }
        return true;
    }
};

complexity

time taken