Minimum Number of Operations to Make Array Empty

medium hash table counting greedy

Problem

You are given an array nums of positive integers. Repeatedly you may delete two elements with equal values, or three elements with equal values. Return the minimum number of operations to empty the array, or -1 if it is impossible.

Elements of different values never interact, so each distinct value is solved on its own. If a value appears with frequency f, the fewest deletions to clear it is ⌈f / 3⌉ (greedily use as many 3-groups as possible, filling the remainder with 2-groups). A value that appears exactly once can never be removed, making the whole task impossible.

Inputnums = [2,3,3,2,2,4,2,3,4]

Output4

Counts: 2→4, 3→3, 4→2. Ops = ⌈4/3⌉ + ⌈3/3⌉ + ⌈2/3⌉ = 2 + 1 + 1 = 4.

nums (comma-separated positive integers)

def minOperations(nums):
    count = {}                       # value -> frequency
    for v in nums:
        count[v] = count.get(v, 0) + 1
    ops = 0
    for f in count.values():
        if f == 1:
            return -1                # a lone value can never be paired
        ops += (f + 2) // 3          # ceil(f / 3): greedy 3s, fill with 2s
    return ops

function minOperations(nums) {
  const count = new Map();           // value -> frequency
  for (const v of nums) count.set(v, (count.get(v) || 0) + 1);
  let ops = 0;
  for (const f of count.values()) {
    if (f === 1) return -1;          // a lone value can never be paired
    ops += Math.floor((f + 2) / 3);  // ceil(f / 3): greedy 3s, fill with 2s
  }
  return ops;
}

int minOperations(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();   // value -> frequency
    for (int v : nums) count.merge(v, 1, Integer::sum);
    int ops = 0;
    for (int f : count.values()) {
        if (f == 1) return -1;       // a lone value can never be paired
        ops += (f + 2) / 3;          // ceil(f / 3): greedy 3s, fill with 2s
    }
    return ops;
}

int minOperations(vector<int>& nums) {
    unordered_map<int, int> count;   // value -> frequency
    for (int v : nums) count[v]++;
    int ops = 0;
    for (auto& [v, f] : count) {
        if (f == 1) return -1;       // a lone value can never be paired
        ops += (f + 2) / 3;          // ceil(f / 3): greedy 3s, fill with 2s
    }
    return ops;
}

Explanation

Because an operation only deletes elements that are equal, values never mix. So the problem decomposes into independent sub-problems, one per distinct value. We use a hash map to count how many times each value occurs in a single linear pass.

For one value with frequency f, the question becomes: what is the fewest number of 2-groups and 3-groups that sum to exactly f? Using as many 3-groups as possible is optimal because a 3-group removes more per operation. Any remainder is then patched with 2-groups.

Concretely, if f % 3 == 0 we use f / 3 triples. If the remainder is 1, we trade one triple for two pairs (e.g. f = 4 = 2 + 2), giving f / 3 + 1 ops. If the remainder is 2, we add one pair, also f / 3 + 1 ops. All three cases collapse to the single formula ⌈f / 3⌉, computed in integer math as (f + 2) / 3.

The only impossible case is f == 1: a single leftover element cannot form a pair or triple, so we immediately return -1. (Note f == 1 is the only bad frequency — every integer ≥ 2 can be written as a combination of 2s and 3s.)

For nums = [2,3,3,2,2,4,2,3,4] the counts are 2→4, 3→3, 4→2, giving 2 + 1 + 1 = 4 operations.

Time: O(n) Space: O(k) distinct values