Zero Array Transformation II - Line Sweep, Binary Search [JS]
Description Solution 1: Binary Search & Line Sweep Binary search for the minimum k , where nums becomes a zero array after k queries. To check whether a value k is valid, Use line sweep to accumulate updates on every range. Accumulate them at the end using prefix sum and check that every nums[i] <= 0 . n = length of nums , m = number of queries Time Complexity: O(n log(m)) Space Complexity: O(n) JavaScript function minZeroArray ( nums , queries ) { const m = queries . length ; let low = 0 , high = m ; while ( low < high ) { const mid = Math . floor ( ( low + high ) / 2 ) ; if ( isValid ( nums , queries , mid ) ) high = mid ; else low = mid + 1 ; } return isValid ( nums , queries , low ) ? low : - 1 ; } ; function isValid ( nums , queries , k ) { const n = nums . length , updates = Array ( n + 1 ) . fill ( 0 ) ; for ( let i = 0 ; i <...