[Leetcode] 3355. Zero Array Transformation I

https://leetcode.com/problems/zero-array-transformation-i/?envType=daily-question&envId=2025-05-20

initial

as we see if we have a long query, this double for loop will cause tle

class Solution {
    public boolean isZeroArray(int[] nums, int[][] queries) {
        int[] count = new int[nums.length];
        for(int[] q : queries){
            for(int i=q[0];i<=q[1];i++) count[i]+=1;
        }
        System.out.println(Arrays.toString(count));
        for(int i=0;i<nums.length;i++){
            nums[i]-=count[i];
            if(nums[i]>0) return false;
        }
        return true;
    }
}

sol

so how to optimise this double for loop? actually if we just mark the start and the end+1 index of this query's effect, then we dont need to calcualte the cumulative effect from start to end index. wat i mean is we dont need to update all indexes but just the start index with increment of +1 and end+1 index of decrement of -1 to mark the end of the effect.

i think indexes are wrong here but u get the point.

Indices: 0  1  2  3  4  5

Query 1:  [0, 3]  -> Mark: freq[0]++, freq[4]--
Query 2:     [2, 5] -> Mark: freq[2]++, freq[6]--
Query 3:  [0, 1]  -> Mark: freq[0]++, freq[2]--

Indices:  0  1  2  3  4  5  6
freq:     +1   0  +1   0  -1   0  -1  (from Query 1 and 2)
          +1   0  -1   0   0   0   0   (from Query 3)
---------------------------------------
Total freq: +2   0   0   0  -1   0  -1

curFreq:  2   2   2   2   1   1   0  (prefix sum)

But wat about the indexes in the middle? how do we know that they are affected too? We can just keep an external variable curFreq and if curFreq<nums[i], there is not enough accumulated frequency to subtract nums[i] to make it 0 or less so we return false.

class Solution {
    public boolean isZeroArray(int[] nums, int[][] queries) {
        int[] count = new int[nums.length];
        for(int[] q : queries){
            count[q[0]]+=1;
            if(q[1]+1 < nums.length)count[q[1]+1]-=1;
        }
        int curFreq=0;
        System.out.println(Arrays.toString(count));
        for(int i=0;i<nums.length;i++){
            curFreq+=count[i];
            if(nums[i]>curFreq) return false;
        }
        return true;
    }
}

complexity

q+ n time
n space