In this guide, you will get 3542. Minimum Operations to Convert All Elements to Zero LeetCode Solution with the best time and space complexity. The solution to Minimum Operations to Convert All Elements to Zero problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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 occurrences of the minimum non-negative integer in that subarray to 0.
Return the minimum number of operations required to make all elements in the array 0.
Example 1:
Input: nums = [0,2]
Output: 1
Explanation:
Select the subarray [1,1] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0].
Thus, the minimum number of operations required is 1.
Example 2:
Input: nums = [3,1,2,1]
Output: 3
Explanation:
Select subarray [1,3] (which is [1,2,1]), where the minimum non-negative integer is 1. Setting all occurrences of 1 to 0 results in [3,0,2,0].
Select subarray [2,2] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [3,0,0,0].
Select subarray [0,0] (which is [3]), where the minimum non-negative integer is 3. Setting all occurrences of 3 to 0 results in [0,0,0,0].
Thus, the minimum number of operations required is 3.
Select subarray [0,5] (which is [1,2,1,2,1,2]), where the minimum non-negative integer is 1. Setting all occurrences of 1 to 0 results in [0,2,0,2,0,2].
Select subarray [1,1] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,2,0,2].
Select subarray [3,3] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,0,0,2].
Select subarray [5,5] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,0,0,0].
Thus, the minimum number of operations required is 4.
Constraints:
1 <= n == nums.length <= 105
0 <= nums[i] <= 105
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
3542. Minimum Operations to Convert All Elements to Zero LeetCode Solution in C++
class Solution {
public:
int minOperations(vector<int>& nums) {
int ans = 0;
stack<int> stack;
stack.push(0);
for (const int num : nums) {
while (!stack.empty() && stack.top() > num)
stack.pop();
if (stack.empty() || stack.top() < num) {
++ans;
stack.push(num);
}
}
return ans;
}
}; /* code provided by PROGIEZ */
3542. Minimum Operations to Convert All Elements to Zero LeetCode Solution in Java
class Solution {
public int minOperations(int[] nums) {
int ans = 0;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
for (final int num : nums) {
while (!stack.isEmpty() && stack.peek() > num)
stack.pop();
if (stack.isEmpty() || stack.peek() < num) {
++ans;
stack.push(num);
}
}
return ans;
}
} // code provided by PROGIEZ
3542. Minimum Operations to Convert All Elements to Zero LeetCode Solution in Python
class Solution:
def minOperations(self, nums: list[int]) -> int:
ans = 0
stack = [0]
for num in nums:
while stack and stack[-1] > num:
stack.pop()
if not stack or stack[-1] < num:
ans += 1
stack.append(num)
return ans # code by PROGIEZ
