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;
}
};