Minimum Number of Operations to Make Array Empty — Solution
Minimum Number of Operations to Make Array Empty solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Number of Operations to Make Array Empty is a medium coding problem on hash table, greedy and counting, asked in Amazon, Google and Swiggy interviews.
- Difficulty: Medium
- Topics: Hash Table, Greedy, Counting
- Asked at: Amazon, Google, Swiggy
- 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 may repeatedly remove two elements with equal value, or three elements with equal value.
Return the minimum number of operations that empties the array, or -1 if it cannot be emptied.
Example 1
Input: nums = [2,3,3,2,2,4,2,3,4]
Output: 4
Explanation: Four 2s, three 3s and two 4s take 2 + 1 + 1 operations.
Example 2
Input: nums = [2,1,2,2,3,3]
Output: -1
Explanation: The single 1 can never be removed.
Example 3
Input: nums = [14,12,14,14,12,14,14,12,12,12,12,14,14,12,14,14,14,12,12]
Output: 7
Constraints
2 <= nums.length <= 1000001 <= nums[i] <= 1000000
Hints for Minimum Number of Operations to Make Array Empty
Hint 1
Values never mix, so each distinct value is an independent subproblem: empty a pile of
fidentical items using twos and threes.Hint 2
A pile of size 1 is impossible; every other size is achievable.
Hint 3
Using as many threes as possible is optimal, and the count works out to
ceil(f / 3).
How to solve Minimum Number of Operations to Make Array Empty
Group by value and solve each pile independently. Emptying a pile of f items with moves of 2 and 3 takes ceil(f / 3) operations, and only f = 1 is impossible.
Approach
- Tally the frequency of each distinct value.
- If any frequency is exactly
1, return-1. - Otherwise add
ceil(f / 3)for every frequency and return the sum.
Why it works
Each operation removes at most 3 items, so at least ceil(f / 3) are needed. That many suffice: write f = 3q + r. For r = 0 use q threes; for r = 1 (and f >= 4) use q - 1 threes and two twos, which is q + 1 = ceil(f/3); for r = 2 use q threes and one two, again q + 1. Only f = 1 has no decomposition.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
ceil(f / 3)in integer arithmetic is(f + 2) / 3, notf / 3 + 1.- Returning
-1only at the end after summing wastes work but is also fine; returning0for an impossible input is not. - Greedily using twos first is not optimal — threes remove more per operation.
Reference solution
Python
from typing import List
def minOperationsEmpty(nums: List[int]) -> int:
count = {}
for x in nums:
count[x] = count.get(x, 0) + 1
ops = 0
for f in count.values():
if f == 1:
return -1
ops += (f + 2) // 3
return opsJava
public static int minOperationsEmpty(int[] nums) {
Map<Integer, Integer> count = new HashMap<>();
for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
int ops = 0;
for (int f : count.values()) {
if (f == 1) return -1;
ops += (f + 2) / 3;
}
return ops;
}C++
int minOperationsEmpty(vector<int>& nums) {
unordered_map<int, int> count;
for (int x : nums) count[x]++;
int ops = 0;
for (auto& e : count) {
if (e.second == 1) return -1;
ops += (e.second + 2) / 3;
}
return ops;
}JavaScript
var minOperationsEmpty = function(nums) {
var count = {};
for (var i = 0; i < nums.length; i++) {
var k = String(nums[i]);
count[k] = (count[k] === undefined ? 0 : count[k]) + 1;
}
var ops = 0;
var keys = Object.keys(count);
for (var j = 0; j < keys.length; j++) {
var f = count[keys[j]];
if (f === 1) return -1;
ops += Math.floor((f + 2) / 3);
}
return ops;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 439 hash table problems · the whole catalogue
Learn the technique: Hashing: Hash Maps and Hash Sets · Greedy Algorithms