Make Array Zero by Subtracting Equal Amounts
EasyPrompt
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
Approaches
4 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It repeatedly finds the smallest non-zero element, subtracts it from all positive elements, and counts the operations until all elements become zero.
Algorithm
- Initialize an
operationscounter to 0. - Enter a loop that continues as long as there are positive numbers in the array.
- Inside the loop, first find the smallest positive number, let's call it
x. - If no positive number is found (all are zero), break the loop.
- If a smallest positive number
xis found, increment theoperationscounter. - Then, iterate through the array again. For every element
nums[i]that is greater than 0, subtractxfrom it:nums[i] = nums[i] - x. - After the loop terminates, return the
operationscount.
Walkthrough
This method follows the problem description literally. In each step, it scans the entire array to find the minimum positive element. If one is found, it increments an operation counter and then scans the array again to subtract this minimum value from all positive elements. This process repeats until all elements in the array are zero.
class Solution { public int minimumOperations(int[] nums) { int operations = 0; while (true) { int minPositive = Integer.MAX_VALUE; boolean allZero = true; for (int num : nums) { if (num > 0) { allZero = false; minPositive = Math.min(minPositive, num); } } if (allZero) { break; } operations++; for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { nums[i] -= minPositive; } } } return operations; }}Complexity
Time
O(U * N), where N is the length of the array and U is the number of unique positive elements. In each of the U operations, we iterate through the array twice (once to find the minimum, once to subtract), which takes O(N) time.
Space
O(1), as we modify the array in-place and use only a few variables for tracking.
Trade-offs
Pros
Simple to understand and directly follows the problem statement.
Requires no extra space.
Cons
Inefficient due to repeated traversals of the array, leading to a quadratic time complexity in the worst case.
This approach improves upon the simulation by first sorting the array. Sorting allows us to process the numbers in increasing order, which simplifies the logic of finding the next smallest element to subtract without repeatedly scanning the array.
Algorithm
- Sort the input array
numsin non-decreasing order. - Initialize
operations = 0andtotalSubtracted = 0. - Iterate through the sorted array
nums. - For each
num, calculate its current value:currentVal = num - totalSubtracted. - If
currentVal > 0, it means we've encountered a new smallest positive number.- Increment
operations. - Add
currentValtototalSubtracted. This simulates subtracting this new smallest value from all subsequent larger numbers.
- Increment
- If
currentValis 0, it means this number has already been reduced to zero by previous operations, so we do nothing. - Return
operations.
Walkthrough
The core idea is that after sorting, we can iterate through the array once. We keep track of the total amount that has been subtracted from all numbers so far. For each number, we check its effective value after subtraction. If it's positive, it represents a new unique value that needs to be zeroed out, so we perform an "operation" and update the total subtracted amount.
import java.util.Arrays; class Solution { public int minimumOperations(int[] nums) { Arrays.sort(nums); int operations = 0; int totalSubtracted = 0; for (int num : nums) { if (num > 0 && num > totalSubtracted) { operations++; totalSubtracted = num; } } return operations; }}Complexity
Time
O(N log N), dominated by the sorting step. The subsequent loop is O(N).
Space
O(log N) or O(N), depending on the sort implementation's space requirements. In Java, `Arrays.sort` for primitives uses a dual-pivot quicksort which has an average space complexity of O(log N).
Trade-offs
Pros
More efficient than the brute-force simulation.
Still conceptually linked to the simulation process but optimized.
Cons
The sorting step is the bottleneck, making it slower than linear-time solutions.
A key insight is that each operation effectively eliminates one unique positive value from the set of numbers present in the array. Therefore, the minimum number of operations is simply the count of unique positive numbers in the initial array. This approach uses a HashSet to efficiently count these unique positive numbers.
Algorithm
- Create an empty
HashSet<Integer>. - Iterate through each number
numin the input arraynums. - If
numis greater than 0, add it to theHashSet. - After the loop, return the size of the
HashSet.
Walkthrough
We can iterate through the array once, adding all positive numbers to a HashSet. A HashSet automatically handles duplicates; adding an existing element has no effect. The final size of the set gives us the count of unique positive numbers, which is the answer.
import java.util.HashSet;import java.util.Set; class Solution { public int minimumOperations(int[] nums) { Set<Integer> uniquePositives = new HashSet<>(); for (int num : nums) { if (num > 0) { uniquePositives.add(num); } } return uniquePositives.size(); }}Complexity
Time
O(N), where N is the length of the array. We iterate through the array once, and each HashSet insertion takes O(1) on average.
Space
O(U), where U is the number of unique positive elements. In the worst case, U can be up to N, so the space complexity is O(N).
Trade-offs
Pros
Simple, elegant, and has an optimal time complexity.
Works for any range of integer values, not just small ones.
Cons
Uses extra space for the HashSet, which might be slightly less efficient in terms of memory and constant factors than a frequency array approach given the problem's constraints.
This is the most efficient approach, leveraging the constraint that array values are between 0 and 100. It uses a boolean array as a direct-address table (or a simple hash set) to track which positive numbers have been seen, thereby counting the unique ones.
Algorithm
- Create a boolean array
seenof size 101, initialized tofalse. - Initialize
count = 0. - Iterate through each number
numinnums. - If
num > 0andseen[num]isfalse, it's the first time we've seen this positive number.- Increment
count. - Mark it as seen:
seen[num] = true.
- Increment
- Return
count.
Walkthrough
Since the numbers are small and non-negative, we can use an array to keep track of the unique positive numbers we've encountered. A boolean array of size 101 is sufficient. The index of the array corresponds to a number, and the value indicates whether that number has been seen. We iterate through the input array, and for each new positive number we encounter, we increment a counter and mark that number as seen in our boolean array.
class Solution { public int minimumOperations(int[] nums) { boolean[] seen = new boolean[101]; int count = 0; for (int num : nums) { if (num > 0 && !seen[num]) { count++; seen[num] = true; } } return count; }}Complexity
Time
O(N), where N is the length of the array. We iterate through the input array once. The size of the `seen` array is constant (101), so it doesn't affect the asymptotic complexity.
Space
O(1). We use a boolean array of a fixed size (101), which is constant space.
Trade-offs
Pros
Optimal time complexity O(N) and optimal constant space complexity O(1).
Very fast in practice due to direct array access with no hashing overhead.
Cons
This specific implementation is only possible because of the tight constraints on the values in
nums(0 to 100). If the numbers could be very large, this approach would be infeasible due to memory limitations.
Solutions
Solution
class Solution {public int minimumOperations(int[] nums) { boolean[] s = new boolean[101]; s[0] = true; int ans = 0; for (int x : nums) { if (!s[x]) { ++ans; s[x] = true; } } return ans; }}class Solution: def minimumOperations( self, nums: List[int]) -> int: return len({x for x in nums if x})class Solution {public: int minimumOperations(vector<int> &nums) { bool s[101]{}; s[0] = true; int ans = 0; for (int &x : nums) { if (!s[x]) { ++ans; s[x] = true; } } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.