leetcode

commit c5bd23a3622d190bd4bc63030a2216bed6055886
parent 1da8c3e659b74cbdbe28645f4d0b8c555b372876
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sun,  9 Nov 2025 22:40:25 -0700

3542. minimum operations to convert all elements to zero

Diffstat:
A
min_ops_convert_elem_zero.c
 | 
36
++++++++++++++++++++++++++++++++++++
A
min_ops_convert_elem_zero.py
 | 
35
+++++++++++++++++++++++++++++++++++

2 files changed, 71 insertions(+), 0 deletions(-)
diff --git a/min_ops_convert_elem_zero.c b/min_ops_convert_elem_zero.c
@@ -0,0 +1,36 @@
+// 3542. Minimum Operations to Convert All Elements to Zero
+#include "leetcode.h"
+
+/*
+ * you are given an array 'nums' of size 'n' consisting of non-negative
+ * integers. your task is to apply some (possibly zero) operations on the array
+ * so that all elements become 0. in one operation, you can select a subarray
+ * '[i, j]' where '0 <= i <= j < n' and set all occurences of the minimum
+ * non-negative integer in that subarray to zero. return the minimum number of
+ * operations required to make all elements in the array 0
+ */
+
+int minOperations(int *nums, int numsSize) {
+  int *stack = (int *)malloc(numsSize * sizeof(int));
+  int top = 0, ans = 0;
+  for (int i = 0; i < numsSize; ++i) {
+    int curr = nums[i];
+    while (top > 0 && stack[top - 1] > curr)
+      --top;
+    if (!curr)
+      continue;
+    if (!top || stack[top - 1] < curr) {
+      ans++;
+      stack[top++] = curr;
+    }
+  }
+  free(stack);
+  return ans;
+}
+
+int main() {
+  int n1[] = {0, 2}, n2[] = {3, 1, 2, 1}, n3[] = {1, 2, 1, 2, 1, 2};
+  printf("%d\n", minOperations(n1, ARRAY_SIZE(n1))); // expect: 1
+  printf("%d\n", minOperations(n2, ARRAY_SIZE(n2))); // expect: 3
+  printf("%d\n", minOperations(n3, ARRAY_SIZE(n3))); // expect: 4
+}
diff --git a/min_ops_convert_elem_zero.py b/min_ops_convert_elem_zero.py
@@ -0,0 +1,35 @@
+# 3542. Minimum Operations to Convert All Elements to Zero
+
+"""
+you are given an array 'nums' of size 'n' consisting of non-negative
+integers. your task is to apply some (possibly zero) operations on the array
+so that all elements become 0. in one operation, you can select a subarray
+'[i, j]' where '0 <= i <= j < n' and set all occurences of the minimum
+non-negative integer in that subarray to zero. return the minimum number of
+operations required to make all elements in the array 0
+"""
+
+
+class Solution(object):
+    def minOperations(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: int
+        """
+        memo = [0] * (len(nums) + 1)
+        top, ans = 0, 0
+        for i in nums:
+            while memo[top] > i:
+                top -= 1
+                ans += 1
+            if memo[top] != i:
+                top += 1
+                memo[top] = i
+        return ans + top
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.minOperations(nums=[0, 2]))
+    print(obj.minOperations(nums=[3, 1, 2, 1]))
+    print(obj.minOperations(nums=[1, 2, 1, 2, 1, 2]))