LeetCode Problem 2870

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Counting

Solution

LeetCode 2870 - Minimum Number of Operations to Make Array Empty

Problem Understanding

The problem gives us an array nums containing positive integers. In a single operation, we are allowed to remove either:

• Exactly 2 equal elements, or
• Exactly 3 equal elements.

Our goal is to remove all elements from the array using the minimum possible number of operations.

A key observation is that elements with different values can never participate in the same operation. If we have values 2 and 3, we cannot combine them in a deletion. Therefore, each distinct value can be processed independently.

The input array may contain up to 10^5 elements, which immediately suggests that we need an efficient solution. Any approach that tries all possible removal combinations would be far too expensive.

The output should be:

• The minimum number of operations required to remove every element.
• -1 if it is impossible to completely empty the array.

The most important part of the problem is determining whether a frequency can be represented as a sum of groups of size 2 and 3.

For example:

• Frequency 2 → one operation.
• Frequency 3 → one operation.
• Frequency 4 → two operations (2 + 2).
• Frequency 5 → two operations (3 + 2).
• Frequency 6 → two operations (3 + 3).

However:

• Frequency 1 → impossible.

This immediately highlights the most important edge case. If any number appears exactly once, there is no valid operation that can remove it, so the answer must be -1.

The constraints guarantee:

• At least two elements exist in the array.
• All values are positive integers.
• Frequencies can be counted efficiently using a hash map.

Approaches

Brute Force

A brute force solution would consider every possible sequence of removing pairs and triples for each value.

Suppose a value appears f times. We could recursively try:

• Remove 2 elements and solve the remaining f - 2.
• Remove 3 elements and solve the remaining f - 3.

Then choose the minimum valid result.

This approach is correct because it explores every possible decomposition of the frequency into groups of 2 and 3.

However, without memoization, the number of recursive states grows exponentially. Even with memoization, it is unnecessary because the structure of the problem allows a much simpler mathematical solution.

Since frequencies can be as large as 10^5, repeatedly exploring combinations would be inefficient.

Key Insight

For a frequency f, we want to partition it into groups of size 2 and 3 while minimizing the number of groups.

Since each operation removes either 2 or 3 elements, fewer operations means we should remove as many triples as possible because a triple removes more elements per operation.

Consider several examples:

Frequency	Best Decomposition	Operations
2	2	1
3	3	1
4	2 + 2	2
5	3 + 2	2
6	3 + 3	2
7	3 + 2 + 2	3
8	3 + 3 + 2	3

A pattern emerges:

• If f == 1, impossible.
• Otherwise, the minimum number of operations is ceil(f / 3).

Why?

Because we maximize the number of triples. Whenever a remainder of 1 would occur, we convert one triple into two pairs.

Examples:

• 4 = 2 + 2
• 7 = 3 + 2 + 2
• 10 = 3 + 3 + 2 + 2

This leads to a simple formula:

$$\text{operations} = \left\lceil \frac{f}{3} \right\rceil$$

which can be computed as:

(f + 2) // 3

for all f >= 2.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^f)	O(f)	Tries all pair/triple decompositions
Optimal	O(n)	O(k)	Count frequencies and apply mathematical formula

Here:

• n = length of nums
• k = number of distinct values

Algorithm Walkthrough

1. Create a hash map that stores the frequency of every value in the array.
2. Initialize a variable operations = 0 to store the total number of required operations.
3. Iterate through every frequency in the hash map.
4. If a frequency equals 1, immediately return -1.

A single occurrence cannot be removed because every operation requires either 2 or 3 equal elements. 5. Otherwise, compute the minimum operations needed for this frequency.

Since we want the largest possible groups, we maximize triples. The minimum number of operations for any frequency f ≥ 2 is:

(f + 2) // 3

6. Add this value to the running total.
7. After processing all frequencies, return the total number of operations.

Why it works

Each distinct value must be processed independently because operations require equal elements. For any frequency f ≥ 2, the optimal strategy is to use as many triples as possible. If maximizing triples leaves a remainder of 1, replacing one triple with two pairs eliminates that remainder while maintaining the minimum number of groups. Therefore, the minimum number of operations for frequency f is exactly ceil(f / 3), and summing these values across all distinct numbers gives the global optimum.

Python Solution

from collections import Counter
from typing import List

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        frequencies = Counter(nums)
        operations = 0

        for count in frequencies.values():
            if count == 1:
                return -1

            operations += (count + 2) // 3

        return operations

The implementation begins by counting how many times each number appears using Counter.

We then iterate through every frequency. If any frequency is exactly 1, we immediately return -1 because there is no valid operation that can remove a single element.

For every other frequency, we add (count + 2) // 3, which is the integer arithmetic equivalent of ceil(count / 3).

Finally, after all frequencies have been processed, we return the accumulated total.

Go Solution

func minOperations(nums []int) int {
	freq := make(map[int]int)

	for _, num := range nums {
		freq[num]++
	}

	operations := 0

	for _, count := range freq {
		if count == 1 {
			return -1
		}

		operations += (count + 2) / 3
	}

	return operations
}

The Go implementation follows exactly the same logic as the Python version.

A map[int]int is used to count frequencies. Integer division naturally performs floor division, so (count + 2) / 3 correctly computes ceil(count / 3) for positive integers. No special handling for overflow is required because the answer is at most on the order of 10^5, well within Go's integer range.

Worked Examples

Example 1

nums = [2,3,3,2,2,4,2,3,4]

Frequency table:

Value	Count
2	4
3	3
4	2

Processing:

Value	Count	Formula	Operations Added
2	4	(4 + 2) // 3 = 2	2
3	3	(3 + 2) // 3 = 1	1
4	2	(2 + 2) // 3 = 1	1

Running total:

Step	Total
Start	0
After count 4	2
After count 3	3
After count 2	4

Result:

4

Example 2

nums = [2,1,2,2,3,3]

Frequency table:

Value	Count
2	3
1	1
3	2

Processing:

Value	Count	Result
2	3	Valid
1	1	Impossible

Since a frequency of 1 is encountered, the algorithm immediately returns:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to count frequencies and one pass through distinct values
Space	O(k)	Hash map stores frequencies of distinct values

The frequency counting step processes each element exactly once. Afterwards, each distinct value is examined once. Therefore the total runtime is linear in the size of the input. The hash map stores one entry per distinct value, resulting in O(k) auxiliary space.

Test Cases

from typing import List

s = Solution()

assert s.minOperations([2,3,3,2,2,4,2,3,4]) == 4  # Example 1
assert s.minOperations([2,1,2,2,3,3]) == -1       # Example 2

assert s.minOperations([1,1]) == 1                # Smallest valid pair
assert s.minOperations([1,1,1]) == 1              # Single triple
assert s.minOperations([1,1,1,1]) == 2            # Two pairs

assert s.minOperations([5,5,5,5,5]) == 2          # 3 + 2
assert s.minOperations([7,7,7,7,7,7]) == 2        # 3 + 3
assert s.minOperations([8,8,8,8,8,8,8]) == 3      # 3 + 2 + 2

assert s.minOperations([1,2,2]) == -1             # Singleton frequency
assert s.minOperations([1,1,2,2,2]) == 2          # Mixed frequencies

assert s.minOperations([4,4,4,4,4,4,4,4]) == 3    # 3 + 3 + 2
assert s.minOperations([9] * 100000) == 33334     # Large input stress test

Test Summary

Test	Why
[2,3,3,2,2,4,2,3,4]	Official example
[2,1,2,2,3,3]	Official impossible case
[1,1]	Minimum valid frequency
[1,1,1]	Single triple
[1,1,1,1]	Requires two pairs
Five equal values	Requires one triple and one pair
Six equal values	All triples
Seven equal values	Triple plus two pairs
[1,2,2]	Singleton frequency causes failure
Mixed frequencies	Multiple independent groups
Eight equal values	Triple, triple, pair
Large stress test	Verifies scalability

Edge Cases

Frequency Equal to One

The most important edge case is when some value appears exactly once. Since every operation removes either two or three equal elements, a single occurrence can never be removed. A common mistake is to blindly apply the formula (count + 2) // 3, which would incorrectly produce 1 for count = 1. The implementation explicitly checks for this condition and immediately returns -1.

Frequencies Leaving Remainder One

Values such as 4, 7, and 10 are tricky because greedily taking triples leaves one leftover element. For example, 7 = 3 + 3 + 1 is invalid. The mathematical formula automatically handles this by effectively converting one triple into two pairs, yielding 7 = 3 + 2 + 2. This ensures the minimum valid number of operations is still computed correctly.

Large Input Sizes

The array length can reach 100000. Any solution that attempts recursive search, dynamic programming over frequencies, or simulation of deletions would be unnecessarily expensive. The implementation only performs frequency counting and simple arithmetic, guaranteeing linear time performance even at the maximum constraint limits.

Multiple Distinct Values

Different values cannot interact during removals. A bug-prone implementation might accidentally try to combine frequencies across values. By using a frequency map and processing each count independently, the solution correctly respects the requirement that every operation must involve equal numbers only.