Skip to main content
Talentd

Minimum Number of Operations to Make Array Empty - Solution & Explanation

MediumArrayHash TableGreedyCounting14 min readAsked at: Amazon, Meta
Practice this problem

Problem Statement

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 <= 105
  • 1 <= 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).

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n), both for listing and iterating through frequencies. Space Complexity: O(n) for the frequency map.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Frequency Count ApproachO(n)O(n)General case. Clean and direct solution using hash map counting.
Greedy Pair-First StrategyO(n)O(n)When explaining the remainder logic in interviews and avoiding leftover single elements.

Video Solution

Minimum Numbers of Operations to Make Array Empty - Leetcode 2870 - Python • NeetCodeIO • 16,949 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Number of Operations to Make Array Empty with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays