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 _theminimum number of operations required to make the array empty, or _-1 if it is not possible.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3

Input: nums = [2,1,2,2,3,3]
Output: -1
Explanation: It is impossible to empty the array.

Constraints

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

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

Solution

Method 1 – Greedy Counting (Minimum Rounds)

Intuition

For each value, we can only remove 2 or 3 at a time. If a value appears once, it’s impossible. Otherwise, we use as many 3-removals as possible, and the rest as 2-removals.

Approach

  1. Count the frequency of each value.
  2. For each frequency:
    • If freq == 1, return -1.
    • Else, minimum operations = ceil(freq / 3).
  3. Sum over all values.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int minOperations(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int n : nums) freq[n]++;
        int ans = 0;
        for (auto& [_, f] : freq) {
            if (f == 1) return -1;
            ans += (f + 2) / 3;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func minOperations(nums []int) int {
    freq := map[int]int{}
    for _, n := range nums { freq[n]++ }
    ans := 0
    for _, f := range freq {
        if f == 1 { return -1 }
        ans += (f + 2) / 3
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import java.util.*;
class Solution {
    public int minOperations(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int n : nums) freq.put(n, freq.getOrDefault(n, 0) + 1);
        int ans = 0;
        for (int f : freq.values()) {
            if (f == 1) return -1;
            ans += (f + 2) / 3;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun minOperations(nums: IntArray): Int {
        val freq = mutableMapOf<Int, Int>()
        for (n in nums) freq[n] = freq.getOrDefault(n, 0) + 1
        var ans = 0
        for (f in freq.values) {
            if (f == 1) return -1
            ans += (f + 2) / 3
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from collections import Counter
class Solution:
    def minOperations(self, nums: list[int]) -> int:
        freq = Counter(nums)
        ans = 0
        for f in freq.values():
            if f == 1:
                return -1
            ans += (f + 2) // 3
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

use std::collections::HashMap;
impl Solution {
    pub fn min_operations(nums: Vec<i32>) -> i32 {
        let mut freq = HashMap::new();
        for n in nums { *freq.entry(n).or_insert(0) += 1; }
        let mut ans = 0;
        for &f in freq.values() {
            if f == 1 { return -1; }
            ans += (f + 2) / 3;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    minOperations(nums: number[]): number {
        const freq = new Map<number, number>();
        for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
        let ans = 0;
        for (const f of freq.values()) {
            if (f === 1) return -1;
            ans += Math.floor((f + 2) / 3);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — n = length of nums.
  • 🧺 Space complexity: O(n) — for frequency map.