3356. Zero Array Transformation II

3356. Zero Array Transformation II

class Solution {
    public int minZeroArray(int[] nums, int[][] queries) {
        int q = queries.length;
        if (!isZeroArray(nums, queries, q)) {
            return -1;
        }

        int left = 0;
        int right = q; // because we are search on 0 to q answer!! so need to use q

        while (left <= right) {
            int mid = left + (right - left)/2;
            if (isZeroArray(nums, queries, mid)) {
                if (mid == 0 || !isZeroArray(nums, queries, mid-1)) { // if mid is 0, means no need any query!
                    return mid;
                }
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
    public boolean isZeroArray(int[] nums, int[][] queries, int k) {
        int n = nums.length;
        int[] sweepLine = new int[n+1];
        for (int i = 0; i < k; i++) {
            int start = queries[i][0];
            int end = queries[i][1];
            int value = queries[i][2];
            sweepLine[start] += value;
            sweepLine[end+1] -= value;
        }
        int reduced = 0;
        for (int i = 0; i < n; i++) {
            reduced += sweepLine[i];
            if (nums[i] > reduced) {
                return false;
            }
        }
        return true;
    }
}
/**

0    3
+.   -
0.   3
+.   -
  1 2
  + -

3356. Zero Array Transformation II
very similar to 3356. Zero Array Transformation I, but now we need only "k" queries
so we can use previous solution (T: O(q+n))
and then use BS to find k in 0~q range, 
so it's time complexity is:
T: O(q+n)logq, q is the len of queries array, n is len of nums array
S: O(n)
 */