3355. Zero Array Transformation I

T: O(nlogn)

S: O(n)

class Solution {
    public boolean isZeroArray(int[] nums, int[][] queries) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int[] q : queries) {
            int start = q[0];
            int end = q[1] + 1;
            map.put(start, map.getOrDefault(start, 0)+1);
            map.put(end, map.getOrDefault(end, 0)-1);
        }
        int cur = 0;
        for (int key : map.keySet()) { // 0: 1 , 3: 0
            int value = map.get(key);
            cur += value;
            map.put(key, cur);
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                continue;
            }
            Integer floorKey = map.floorKey(i);
            //System.out.println(floorKey + ", v=" + map.get(floorKey));
            if (floorKey == null || map.get(floorKey) < nums[i]) {
                return false;
            }
        }
        return true;
    }
}

/***

  1 2 3
0 1 2

-1 -2 -2 -1

1 0 1
1 1 1

  1.  3 4
0.  2 
+
  +   - -

1 2 2 1 0


[0,2]
0.  3
1.  0  
 */

because the traget is limited, so can use bucket sort

T: O(n+q)

S: O(n)

class Solution {
    public boolean isZeroArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] freq = new int[n+1];
        for (int[] q : queries) {
            int start = q[0];
            int end = q[1]+1;
            freq[start]++; // 0: 8
            freq[end]--;   // 1: 6
                           // 2: -14
        }
        //System.out.println(Arrays.toString(freq));
        int cur = 0;
        for (int i = 0 ; i < n; i++) {
            cur += freq[i];
            if (nums[i] == 0) {
                continue;
            }
            if (cur < nums[i]) {
                return false;
            }
        }
        return true;
    }
}
/**
nums = [0,10]
q= [[0,0],[0,1],[1,1],[0,1],[1,1],[1,1],[1,1],[1,1],[0,1],[0,1],[0,1],[0,1],[1,1],[0,1],[1,1]]

            freq[start]++; // 0: 8 (+1
            freq[end]--;   // 1: 6 (+2
                           // 2: -14

line sweep store the count info for start and end

so continuous start, should be accumalating ...
0: 8 means 0 to 1 , has 8 count
1: means 1 to 1 has 6 count (so need to add 8)

0   1  2
+8-------

   +6 -14


*/