Minimum Number of Operations to Make Array Empty solution and explanation
9 more videos on this problem
Minimum Numbers of Operations to Make Array Empty - Leetcode 2870 - PythonNeetCodeIO · 10:12 · 16K views
Minimum Number of Operations to Make Array Empty | Explained with Reasons | Greedy | Leetcode 2870codestorywithMIK · 20:21 · 6K views
2870. Minimum Number of Operations to Make Array EmptyAryan Mittal · 10:03 · 1K views
2870. Minimum Number of Operations to Make Array Empty || Frequency count 🔥Ayush Rao · 4:53 · 1K views
Leetcode | 2870. Minimum Number of Operations to Make Array Empty | Medium | Java SolutionDeveloper Docs · 10:18 · 764 views
Daily Leetcode #1374: Jan 04, 2024 - 2870. Minimum Number of Operations to Make Array EmptyProgramming Live with Larry · 11:38 · 483 views
2870. Minimum Number of Operations to Make Array Empty (Leetcode Medium)Programming Live with Larry · 5:07 · 453 views
Solving LeetCode 2870 Minimum Number of Operations to Make Array Empty | HashTable | Greedy | AppleCode Harmony · 11:58 · 216 views
LeetCode 2870 - Minimum Number of Operations to Make Array Empty - PythonAlpha-Code · 13:22 · 128 views
2870. Minimum Number of Operations to Make Array Empty || Biweekly Contest 114 || LeetcodeAshish Kumar · 4:14 · 119 views
The problem
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:
- Choose two elements with equal values and delete them from the array.
- Choose three elements with equal values and delete them from the array.
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.
Approach overview
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.
Approach 1: Frequency Count Approach
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).
from collections import Counter
def min_operations(nums):
freq = Counter(nums)
operations = 0
for count in freq.values():
if count == 1:
return -1
op = count // 3
if count % 3 != 0:
op += 1
operations += op
return operationsimport java.util.HashMap;
public class Solution {
public int minOperations(int[] nums) {
HashMap<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
int operations = 0;
for (int count : freq.values()) {
if (count == 1) return -1;
operations += (count + 2) / 3;
}
return operations;
}
}#include <vector>
#include <unordered_map>
#include <cmath>
int minOperations(std::vector<int>& nums) {
std::unordered_map<int, int> freq;
for (int num : nums) {
freq[num]++;
}
int operations = 0;
for (auto it : freq) {
int count = it.second;
if (count == 1) return -1;
operations += std::ceil((double)count / 3);
}
return operations;
}function minOperations(nums) {
const freq = {};
nums.forEach(num => {
freq[num] = (freq[num] || 0) + 1;
});
let operations = 0;
for (let count of Object.values(freq)) {
if (count === 1) return -1;
operations += Math.ceil(count / 3);
}
return operations;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinOperations(int[] nums) {
Dictionary<int, int> freq = new Dictionary<int, int>();
foreach (var num in nums) {
if (!freq.ContainsKey(num)) {
freq[num] = 0;
}
freq[num]++;
}
int operations = 0;
foreach (var kvp in freq) {
int count = kvp.Value;
if (count == 1) return -1;
operations += (count + 2) / 3;
}
return operations;
}
}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.
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.
Approach 2: Greedy Pair-First Strategy
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.
from collections import Counter
def min_operations(nums):
freq = Counter(nums)
operations = 0
for count in freq.values():
if count == 1:
return -1
while count >= 2:
if count == 2 or count == 5:
count -= 2
else:
count -= 3
operations += 1
return operationsimport java.util.HashMap;
public class Solution {
public int minOperations(int[] nums) {
HashMap<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
int operations = 0;
for (int count : freq.values()) {
if (count == 1) return -1;
while (count >= 2) {
if (count == 2 || count == 5) {
count -= 2;
} else {
count -= 3;
}
operations++;
}
}
return operations;
}
}#include <vector>
#include <unordered_map>
int minOperations(std::vector<int>& nums) {
std::unordered_map<int, int> freq;
for (int num : nums) {
freq[num]++;
}
int operations = 0;
for (auto it : freq) {
int count = it.second;
if (count == 1) return -1;
while (count >= 2) {
if (count == 2 || count == 5) {
count -= 2;
} else {
count -= 3;
}
operations++;
}
}
return operations;
}function minOperations(nums) {
const freq = {};
nums.forEach(num => {
freq[num] = (freq[num] || 0) + 1;
});
let operations = 0;
for (let count of Object.values(freq)) {
if (count === 1) return -1;
while (count >= 2) {
if (count === 2 || count === 5) {
count -= 2;
} else {
count -= 3;
}
operations++;
}
}
return operations;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinOperations(int[] nums) {
Dictionary<int, int> freq = new Dictionary<int, int>();
foreach (var num in nums) {
if (!freq.ContainsKey(num)) {
freq[num] = 0;
}
freq[num]++;
}
int operations = 0;
foreach (var kvp in freq) {
int count = kvp.Value;
if (count == 1) return -1;
while (count >= 2) {
if (count == 2 || count == 5) {
count -= 2;
} else {
count -= 3;
}
operations++;
}
}
return operations;
}
}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.
Time Complexity: O(n), both for listing and iterating through frequencies. Space Complexity: O(n) for the frequency map.
Approach 3: Hash Table + Greedy
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).
function minOperations(nums: number[]): number {
const count: Map<number, number> = new Map();
for (const num of nums) {
count.set(num, (count.get(num) ?? 0) + 1);
}
let ans = 0;
for (const [_, c] of count) {
if (c < 2) {
return -1;
}
ans += ((c + 2) / 3) | 0;
}
return ans;
}func minOperations(nums []int) (ans int) {
count := map[int]int{}
for _, num := range nums {
count[num]++
}
for _, c := range count {
if c < 2 {
return -1
}
ans += (c + 2) / 3
}
return
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Minimum Number of Operations to Make Array Empty easy or hard?
The problem is rated Medium because the implementation is simple but the key insight is recognizing the greedy pattern for handling frequencies and the remainder case where f % 3 equals 1.
Minimum Number of Operations to Make Array Empty Python/Java solution
Implementations typically build a dictionary or HashMap to count frequencies, then compute operations using greedy math on each count. The same logic works across Python, Java, C++, C#, and JavaScript with identical O(n) complexity.
How to solve Minimum Number of Operations to Make Array Empty in O(n)?
First count occurrences of each number using a hash map. For every frequency f, compute the minimum operations using greedy grouping of triplets and pairs. If f equals 1 return -1; otherwise add ceil(f / 3) operations. This produces a linear time O(n) algorithm.
What is the best approach for Minimum Number of Operations to Make Array Empty?
The optimal approach counts the frequency of each value using a hash map and then greedily removes elements in groups of three whenever possible. For a frequency f, the minimum operations equal ceil(f / 3), except when f = 1 which makes the task impossible. This method runs in O(n) time with O(n) space.
Is Minimum Number of Operations to Make Array Empty asked at Google/Amazon/Meta?
Problems combining frequency counting and greedy grouping frequently appear in interviews at companies like Amazon, Google, and Meta. Variations test whether candidates recognize that operations depend on counts rather than element order.
What data structure is used in Minimum Number of Operations to Make Array Empty?
A hash table (dictionary or unordered_map) stores the frequency of each integer. This enables constant-time updates while counting elements and allows processing each unique value independently.
What is the time complexity of Minimum Number of Operations to Make Array Empty?
The optimal solution runs in O(n) time because the array is scanned once to build a frequency map and each unique value is processed once. Space complexity is O(n) due to storing counts in a hash table.