Minimum Number of Operations to Make Array Empty

How it works

There is a mathematical pattern: for any count greater than 1, the minimum operations is the ceiling of count / 3. This works because we prioritize groups of 3, and any remainder can be handled by converting some 3s to 2s. For example, count = 4 uses two 2s, count = 5 uses one 2 and one 3.

The only impossible case is when count equals 1, since we need at least 2 identical elements to perform any deletion.

Steps

1. Count the frequency of each element.
2. For each frequency:
   • If it equals 1, return -1 (impossible).
   • Otherwise, add ceil(count / 3) to the res.
3. Return the total operations.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Forgetting the Impossible Case

When an element appears exactly once, it is impossible to delete it since the minimum group size is 2. Failing to check for frequencies of 1 and return -1 will produce incorrect results for inputs that cannot be emptied.

Using Division Instead of Ceiling

The greedy solution requires ceiling division (ceil(count / 3)), not floor division. Using count / 3 will undercount operations for counts like 4, 5, 7, or 8 where remainders require additional groups.

Integer Overflow When Adding One

In some languages, when using the formula (count + 2) / 3 for ceiling division, adding 2 to a very large count could cause overflow. While unlikely given typical constraints, be aware of this when working with custom large inputs.

from typing import List
from collections import Counter
import math

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

        for num, cnt in count.items():
            if cnt == 1:
                return -1
            res += math.ceil(cnt / 3)

        return res

class Solution {
public:
    int minOperations(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }

        int res = 0;
        for (auto& [num, cnt] : count) {
            if (cnt == 1) {
                return -1;
            }
            res += (cnt + 2) / 3;
        }

        return res;
    }
};