Time: 24 ms (100.00%), Space: 116.3 MB (100.00%) - LeetHub

py3-coder · py3-coder · commit 37b0bc008c4b · 2024-11-18T14:29:58.000+05:30
diff --git a/3356-zero-array-transformation-ii/3356-zero-array-transformation-ii.java b/3356-zero-array-transformation-ii/3356-zero-array-transformation-ii.java
@@ -0,0 +1,44 @@
+class Solution {
+    public int minZeroArray(int[] nums, int[][] queries) {
+         // Sweep Line ALgo :-
+        int start = 0;
+        int end = queries.length;
+        int ans = -1;
+
+        while (start <= end) {
+            int mid = start + (end - start) / 2;
+            if (isPossible(nums, queries, mid)) {
+                ans = mid;
+                end = mid - 1;
+            } else {
+                start = mid + 1;
+            }
+        }
+
+        return ans;
+    }
+    
+    public boolean isPossible(int[] nums, int[][] queries,int k){
+        int n = nums.length;
+        
+        int[] line = new int[n+1];
+        
+        for(int idx = 0; idx < k; idx++){
+            line[queries[idx][0]] += queries[idx][2];
+            line[queries[idx][1] + 1] -= queries[idx][2];
+        }
+        
+        if (line[0] < nums[0]) {
+            return false;
+        }
+        
+        for(int i=1;i<n;i++){
+            line[i] = line[i]+line[i-1];
+            
+            if(line[i]<nums[i]){
+                return false;
+            }
+        }
+        return true;
+    }
+}
