# Minimum Number of Operations to Make Array Empty
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-operations-to-make-array-empty)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-operations-to-make-array-empty
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## 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 <= 105`
* `1 <= nums[i] <= 106`

**Note:** This question is the same as [2244: Minimum Rounds to Complete All Tasks.](https://leetcode.com/problems/minimum-rounds-to-complete-all-tasks/description/)

# Approaches
## Approach 1: Sorting and Counting
This approach involves sorting the array first to group identical elements together. After sorting, we can iterate through the array once to count the frequency of each number and calculate the minimum operations required for each group.
**Time:** O(N log N), where N is the length of the `nums` array. The sorting step dominates the time complexity. The subsequent linear scan to count elements takes O(N) time. · **Space:** O(log N) to O(N). The space complexity depends on the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a variant of Quicksort, which requires O(log N) space on average for the recursion stack, but can be O(N) in the worst case.
**Pros:** Conceptually straightforward after realizing sorting helps group elements.; Can be implemented with a single pass after sorting.
**Cons:** The time complexity is dominated by the sorting step, making it less efficient than a hash map-based approach.; Sorting might require additional space depending on the algorithm used.
### Explanation
The fundamental insight is that operations only apply to elements of equal value. By sorting the array, all identical elements become adjacent, which simplifies the process of counting them. We can then iterate through the sorted array, identify blocks of identical numbers, and for each block, calculate the minimum operations needed to clear it.

For a group of `count` identical elements:
- If `count` is 1, it's impossible to clear, so we return -1.
- Otherwise, we need to express `count` as `2*a + 3*b` such that the total operations `a + b` is minimized. This is achieved by maximizing `b` (the number of 3-element deletions). 
- A concise mathematical formula to calculate the minimum operations for a given `count > 1` is `(count + 2) / 3` using integer division. This covers all cases:
  - If `count % 3 == 0`, ops = `count / 3`.
  - If `count % 3 == 1` (e.g., 4), we need two 2-element ops. `(4+2)/3 = 2`.
  - If `count % 3 == 2` (e.g., 5), we need one 3-element and one 2-element op. `(5+2)/3 = 2`.

```java
import java.util.Arrays;

class Solution {
    public int minOperations(int[] nums) {
        Arrays.sort(nums);
        int totalOps = 0;
        int i = 0;
        while (i < nums.length) {
            int j = i;
            while (j < nums.length && nums[j] == nums[i]) {
                j++;
            }
            int count = j - i;
            if (count == 1) {
                return -1;
            }
            totalOps += (count + 2) / 3;
            i = j;
        }
        return totalOps;
    }
}
```
### Algorithm
*   Sort the input array `nums` to group identical elements together.
*   Initialize a variable `totalOperations` to 0.
*   Iterate through the sorted array from left to right.
*   For each unique element, count its occurrences. Let the count be `c`.
*   If `c` is 1, it's impossible to remove this element, so return -1.
*   To find the minimum operations for `c` elements, we should maximize the use of 3-element deletions. The number of operations can be calculated with the formula `(c + 2) / 3`.
*   Add the result to `totalOperations`.
*   Continue until all elements are processed.
*   Return `totalOperations`.

## Approach 2: Frequency Counting with a Hash Map
A more efficient approach is to use a hash map to count the frequency of each number in the array. This avoids the O(N log N) cost of sorting and allows us to process the counts directly in linear time.
**Time:** O(N), where N is the number of elements in the array. We perform a single pass to build the frequency map (O(N)) and another pass over the unique elements (at most N unique elements) to calculate the total operations. This results in an overall linear time complexity. · **Space:** O(K), where K is the number of unique elements in the array. In the worst-case scenario where all N elements are distinct, the space complexity becomes O(N).
**Pros:** Optimal time complexity of O(N).; Directly solves the problem by focusing on frequencies, which is the core of the problem.
**Cons:** Requires extra space to store the frequency map, which can be up to O(N) if all elements are unique.
### Explanation
Since the order of elements in the array is irrelevant for the operations, the problem can be reduced to a frequency counting problem. A hash map is an ideal data structure for this, as it provides average O(1) time for insertions and lookups.

First, we iterate through the input array `nums` once to build a map from each number to its frequency. Then, we iterate through the frequencies (the values of the map). For each frequency `count`, we determine the minimum number of operations.

- If any number has a frequency of 1, we can never remove it, as operations require at least two equal elements. In this case, we return -1.
- For any other frequency `count`, we want to clear it using a mix of 2-element and 3-element deletions. To minimize the number of operations, we should use as many 3-element deletions as possible. The optimal number of operations for a given `count` can be calculated as `ceil(count / 3.0)`, which can be implemented in integer arithmetic as `(count + 2) / 3`.

This approach is optimal because it processes the array in a single pass to get counts and then processes each unique element's count once.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int minOperations(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        int totalOps = 0;
        for (int count : counts.values()) {
            if (count == 1) {
                return -1;
            }
            totalOps += (count + 2) / 3;
        }
        return totalOps;
    }
}
```
### Algorithm
*   Create a `HashMap` to store the frequency of each number in the `nums` array.
*   Iterate through `nums` and populate the frequency map. This takes O(N) time.
*   Initialize a variable `totalOperations` to 0.
*   Iterate through the values (frequencies) in the hash map.
*   For each frequency `count`:
    *   If `count` is 1, it's impossible to clear the array. Return -1 immediately.
    *   Calculate the minimum operations required for `count` elements using the formula `(count + 2) / 3`.
    *   Add this number to `totalOperations`.
*   After checking all frequencies, return `totalOperations`.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int num : nums) {
```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<int> &nums) {
    unordered_map<int, int> count;
    for (int num : nums) {
      ++count[num];
    }
    int ans = 0;
    for (auto &[_, c] : count) {
      if (c < 2) {
        return -1;
      }
      ans += (c + 2) / 3;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minOperations(self, nums: List[int]) -> int: count = Counter(nums) ans = 0 for c in count . values(): if c == 1: return - 1 ans += (c + 2) // 3 return ans

```