Watch 10 video solutions for Make Array Zero by Subtracting Equal Amounts, a easy level problem involving Array, Hash Table, Greedy. This walkthrough by Bro Coders has 3,783 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |