Make Array Zero by Subtracting Equal Amounts - Solution & Explanation
Problem Statement
You are given a non-negative integer array nums. In one operation, you must:
- Choose a positive integer
xsuch thatxis less than or equal to the smallest non-zero element innums. - Subtract
xfrom every positive element innums.
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] <= 100
Approach Overview
Problem 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.
Approach 1: Approach 1: Count Unique Non-Zero Elements
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.
Complexity
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.
Approach 2: Approach 2: Sort and Count Changes
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.
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since we're sorting in place and using constant extra space.
Approach 3: Hash Table or Array
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.
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
2357. Make Array Zero by Subtracting Equal Amounts || Leetcode Weekly Contest 304 • Bro Coders • 3,877 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Make Array Zero by Subtracting Equal Amounts easy or hard?
Make Array Zero by Subtracting Equal Amounts Python/Java solution
How to solve Make Array Zero by Subtracting Equal Amounts in O(n)?
What is the best approach for Make Array Zero by Subtracting Equal Amounts?
Is Make Array Zero by Subtracting Equal Amounts asked at Google/Amazon/Meta?
What data structure is used in Make Array Zero by Subtracting Equal Amounts?
What is the time complexity of Make Array Zero by Subtracting Equal Amounts?
Ready to solve this problem?
Practice Make Array Zero by Subtracting Equal Amounts with our built-in code editor and test cases.
Practice on FleetCode