[Leetcode] 356. Zero Array Transformation II

https://leetcode.com/problems/zero-array-transformation-ii/description/

initial

so i managed to solve. We use binary search to guess how many queries we need to make nums array's elements all 0. And with line sweep, we mark Start index and end index +1. Dont forget to mark end index +1 PLUS ONE PLUS ONE!!!! I forgot and got an error

sol

class Solution {
    public int minZeroArray(int[] nums, int[][] queries) {
        int left=0;
        int right= queries.length+1;
        int ans = Integer.MAX_VALUE;
        int n = nums.length;
        while(left<right){
            int mid = left+ (right-left)/2;
            int[] count = new int[n];
            for(int i=0;i<mid;i++){
                int[] query = queries[i];
                int start = query[0], end = query[1], val = query[2];
                count[start]+=val;
                if(end+1<n) count[end+1]-=val;
            }
            int zeroCount = 0;
            int cur=0;
            for(int i=0;i<n;i++){
                cur+=count[i];
                if(cur>=nums[i]) zeroCount+=1;
            }
            if(zeroCount<n) left=mid+1;
            else{
                ans=Math.min(ans,mid);
                right=mid;
            }
        }
        return ans==Integer.MAX_VALUE? -1 : ans;
    }
}

complexity

log q binary search and we iterate for q and n within binary search so
log q * (q+n) time
the count array is the main space n so n space.