You are given a non-negative integer array nums. In one operation, you must:
x such that x is less than or equal to the smallest non-zero element in nums.x from every positive element in nums.Return the minimum number of operations to make every element in nums equal to 0.
Example 1:
Input: nums = [1,5,0,3,5] Output: 3 Explanation: In the first operation, choose x = 1. Now, nums = [0,4,0,2,4]. In the second operation, choose x = 2. Now, nums = [0,2,0,0,2]. In the third operation, choose x = 2. Now, nums = [0,0,0,0,0].
Example 2:
Input: nums = [0] Output: 0 Explanation: Each element in nums is already 0 so no operations are needed.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 100Problem Overview: You are given an integer array nums. In one operation, choose a positive integer x that is less than or equal to the smallest non‑zero element and subtract x from every positive element in the array. The goal is to count how many operations are required to make every element equal to zero.
Approach 1: Count Unique Non-Zero Elements (O(n) time, O(n) space)
The key observation is that each operation removes one distinct positive value level from the array. If the array contains values like [1,3,5], the operations correspond to subtracting the smallest remaining positive number each time, effectively collapsing the array level by level. That means the total operations equal the number of distinct non-zero values. You iterate through the array, insert every positive value into a set, and return the size of that set. This approach relies on fast hash lookups and avoids simulation entirely. It is the most efficient solution and directly leverages properties of array traversal and hash table uniqueness.
Approach 2: Sort and Count Changes (O(n log n) time, O(1) extra space)
Another way to view the problem is through ordering. After sorting the array, identical numbers appear together and increasing values represent new subtraction levels. Traverse the sorted array and count how many times the value changes from one positive number to a larger one. Each change represents a new operation because you must subtract the next smallest remaining value. Skip zeros at the beginning, then increment the operation counter whenever nums[i] > nums[i-1]. This method uses sorting to simplify the logic and works well when in-place processing is preferred.
Recommended for interviews: The unique non-zero count approach is the cleanest and runs in linear time. Interviewers expect candidates to recognize the greedy insight that each distinct positive value represents one subtraction round. The sorting approach still demonstrates good reasoning about value transitions but has higher time complexity due to sorting.
This approach is based on the observation that the number of operations required to make all elements zero is equal to the number of unique non-zero elements in the array. This is because, in each operation, we can choose a different positive integer, which effectively removes that integer from all the non-zero elements until all are reduced to zero.
We use an array uniqueNonZero to track unique non-zero elements. For each element in nums, if it's greater than zero, it is flagged in the uniqueNonZero array. Finally, we count and return the total number of flagged elements which corresponds to the minimum number of operations required.
Time Complexity: O(n + m) where n is the number of elements in nums and m is the number of possible unique values (bounded by 100).
Space Complexity: O(1) as the space used does not scale with input size.
In this approach, we sort the array and traverse it while counting the transitions from one unique non-zero element to the next, which will ultimately give us the number of operations required.
The array is sorted first. We traverse the sorted array, counting each unique non-zero transition, which equals the desired operation count.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since we're sorting in place and using constant extra space.
We observe that in each operation, all identical nonzero elements in the array nums can be reduced to 0. Therefore, we only need to count the number of distinct nonzero elements in nums, which is the minimum number of operations required. To count the distinct nonzero elements, we can use a hash table or an array.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Approach 1: Count Unique Non-Zero Elements | Time Complexity: O(n + m) where n is the number of elements in nums and m is the number of possible unique values (bounded by 100). |
| Approach 2: Sort and Count Changes | Time Complexity: O(n log n) due to sorting. |
| Hash Table or Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count Unique Non-Zero Elements | O(n) | O(n) | Best general solution; fast linear scan using a hash set |
| Sort and Count Changes | O(n log n) | O(1) extra (in-place sort) | Useful when sorting is already required or avoiding extra hash memory |
2357. Make Array Zero by Subtracting Equal Amounts || Leetcode Weekly Contest 304 • Bro Coders • 3,783 views views
Watch 9 more video solutions →Practice Make Array Zero by Subtracting Equal Amounts with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor