Make Array Zero by Subtracting Equal Amounts — Solution
Make Array Zero by Subtracting Equal Amounts solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Make Array Zero by Subtracting Equal Amounts is an easy coding problem on arrays, hash table and sorting, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Sorting, Greedy, Simulation, Heap
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of non-negative integers. In one operation you:
- choose a positive integer
xno larger than the smallest non-zero element ofnums, and - subtract
xfrom every positive element.
Return the minimum number of operations needed to make every element of nums equal to 0.
Example 1
Input: nums = [4,0,4,2,2]
Output: 2
Explanation: Subtract 2: `[2,0,2,0,0]`. Subtract 2 again: all zeros.
Example 2
Input: nums = [0,0]
Output: 0
Explanation: The array is already all zeros.
Example 3
Input: nums = [7,1,3,7,1]
Output: 3
Explanation: Subtract 1, then 2, then 4: the distinct values 1, 3 and 7 each need their own step.
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 100
Hints for Make Array Zero by Subtracting Equal Amounts
Hint 1
Subtracting the smallest positive element each time is never worse than subtracting less.
Hint 2
Each such operation turns every copy of the current minimum into 0 and keeps distinct values distinct.
Hint 3
So the answer is the number of distinct positive values.
How to solve Make Array Zero by Subtracting Equal Amounts
Equal elements stay equal through every operation, and each operation can zero out at most one group of equal values (the smallest). Taking x = the current minimum does exactly that, so the answer is the count of distinct non-zero values.
Approach
- Insert every positive element into a set.
- Return the size of the set.
Why it works
An operation subtracts the same amount from every positive element, so two positive elements that differ keep differing until the smaller reaches 0 — they can never reach 0 in the same operation. Hence at least one operation per distinct positive value is needed. Choosing x equal to the smallest positive value zeroes exactly that value's group each time, meeting the bound.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Zero is not counted — elements already at 0 are untouched.
- Duplicates collapse into one operation; counting elements instead of distinct values overcounts.
Reference solution
Python
from typing import List
def minimumOperations(nums: List[int]) -> int:
return len({x for x in nums if x > 0})Java
public static int minimumOperations(int[] nums) {
boolean[] seen = new boolean[101];
int count = 0;
for (int x : nums) {
if (x > 0 && !seen[x]) { seen[x] = true; count++; }
}
return count;
}C++
int minimumOperations(vector<int>& nums) {
unordered_set<int> seen;
for (int x : nums) if (x > 0) seen.insert(x);
return (int)seen.size();
}JavaScript
var minimumOperations = function(nums) {
var seen = new Set();
for (var i = 0; i < nums.length; i++) if (nums[i] > 0) seen.add(nums[i]);
return seen.size;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets