You are given a 0-indexed array nums consisting of positive integers.
There are two types of operations that you can apply on the array any number of times:
Return the minimum number of operations required to make the array empty, or -1 if it is not possible.
Example 1:
Input: nums = [2,3,3,2,2,4,2,3,4] Output: 4 Explanation: We can apply the following operations to make the array empty: - Apply the first operation on the elements at indices 0 and 3. The resulting array is nums = [3,3,2,4,2,3,4]. - Apply the first operation on the elements at indices 2 and 4. The resulting array is nums = [3,3,4,3,4]. - Apply the second operation on the elements at indices 0, 1, and 3. The resulting array is nums = [4,4]. - Apply the first operation on the elements at indices 0 and 1. The resulting array is nums = []. It can be shown that we cannot make the array empty in less than 4 operations.
Example 2:
Input: nums = [2,1,2,2,3,3] Output: -1 Explanation: It is impossible to empty the array.
Constraints:
2 <= nums.length <= 1051 <= nums[i] <= 106
Note: This question is the same as 2244: Minimum Rounds to Complete All Tasks.
Problem Overview: You are given an array of integers. In one operation, you can remove either 2 or 3 equal values from the array. The goal is to empty the array using the minimum number of operations. If any value appears only once, the task becomes impossible because no operation removes a single element.
Approach 1: Frequency Count Approach (O(n) time, O(n) space)
The key observation is that operations only depend on how many times each value appears. Build a frequency map using a hash table and process each distinct number independently. For a value appearing f times, the optimal strategy is to remove as many triplets as possible since they eliminate more elements per operation. The minimum operations become ceil(f / 3), except when f = 1, which immediately makes the answer -1. Implementation involves iterating through the array once, storing counts in a hash map, then computing the operations per frequency. This approach relies heavily on hash table counting and works in linear time.
Approach 2: Greedy Pair-First Strategy (O(n) time, O(n) space)
A greedy variation focuses on avoiding the problematic remainder case when the frequency leaves a single element. After counting occurrences, check the remainder when dividing by three. If f % 3 == 0, use only triplet removals. If f % 3 == 2, one pair plus the rest triplets works. The tricky case is f % 3 == 1. Removing only triplets would leave one element, so you convert one triplet into two pairs instead. That adjustment keeps the array removable while still minimizing operations. This greedy reasoning ensures the minimal number of operations while scanning frequencies from the array counts stored in the map. The logic mirrors many greedy problems where a local adjustment prevents an invalid leftover state.
Recommended for interviews: The frequency counting approach combined with the greedy formula is what interviewers expect. It demonstrates recognition that the problem reduces to independent frequency groups rather than element positions. A brute force simulation of removals would be inefficient and unnecessary. Explaining why the remainder 1 case converts a triplet into two pairs shows deeper greedy reasoning and usually earns full credit.
This approach leverages the frequency count of each number to determine the minimum number of operations needed. We will iterate over the frequency list and for each number, calculate the possible number of operations (either removing two or three elements at a time).
We first use Counter from collections to get the frequency of each number in the array. Then, for each frequency, we calculate how many pairs or triples can be removed. We need at least pairs to remove numbers, so if a number appears only once in the list, we return -1. Otherwise, we take the integer division by 3 to count the full groups of 3 elements and add one more operation if there's a remainder. This approach results in efficient calculations to find the minimum operations.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n), where n is the length of the array, as we are iterating through the array and frequencies. Space Complexity: O(n) for storing the frequency count.
This approach targets optimizing operations by prioritizing pair removals wherever possible, then triples. The main idea is to use as many pair removals as possible, and only use triples to fill gaps that pairs cannot cover fully.
Using Counter for frequency counts, we iterate through controlling operations greedily by continuously subtracting 3 (for triples) unless only a single pair remains. This logic ensures minimal operations by prioritizing large removals over small ones unless strictly necessary.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n), both for listing and iterating through frequencies. Space Complexity: O(n) for the frequency map.
We use a hash table count to count the number of occurrences of each element in the array. Then we traverse the hash table. For each element x, if it appears c times, we can perform \lfloor \frac{c+2}{3} \rfloor operations to delete x. Finally, we return the sum of the number of operations for all elements.
The time complexity is O(n), where n is the length of the array. The space complexity is O(n).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Frequency Count Approach | Time Complexity: O(n), where n is the length of the array, as we are iterating through the array and frequencies. Space Complexity: O(n) for storing the frequency count. |
| Greedy Pair-First Strategy | Time Complexity: O(n), both for listing and iterating through frequencies. Space Complexity: O(n) for the frequency map. |
| Hash Table + Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Count Approach | O(n) | O(n) | General case. Clean and direct solution using hash map counting. |
| Greedy Pair-First Strategy | O(n) | O(n) | When explaining the remainder logic in interviews and avoiding leftover single elements. |
Minimum Numbers of Operations to Make Array Empty - Leetcode 2870 - Python • NeetCodeIO • 16,788 views views
Watch 9 more video solutions →Practice Minimum Number of Operations to Make Array Empty with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor