Problem Description

You have an array nums containing positive integers (0-indexed). You can perform two types of operations on this array as many times as needed:

1. Delete 2 elements - Pick any two elements that have the same value and remove them from the array
2. Delete 3 elements - Pick any three elements that have the same value and remove them from the array

Your goal is to find the minimum number of operations needed to completely empty the array. If it's impossible to empty the array using these operations, return -1.

For example, if you have the array [2, 2, 3, 3, 3]:

• You can delete the two 2's using one operation (type 1)
• You can delete the three 3's using one operation (type 2)
• Total: 2 operations to empty the array

The key insight is that for any value appearing c times:

• If c = 1, it's impossible to delete (return -1)
• If c = 2, use one type-1 operation
• If c = 3, use one type-2 operation
• If c = 4, use two type-1 operations
• If c = 5, use one type-1 and one type-2 operation
• And so on...

The pattern shows that for any count c ≥ 2, the minimum operations needed is ⌊(c + 2) / 3⌋. This formula gives us the optimal way to combine operations of deleting 2 or 3 elements to minimize the total number of operations.

Intuition

Let's think about what happens when we have a value that appears c times. We need to remove all c occurrences using operations that remove either 2 or 3 elements at a time.

First, if c = 1, we can't remove it at all since both operations require at least 2 elements. So we return -1.

For any c ≥ 2, we want to minimize the number of operations. Let's explore some cases:

• c = 2: Use 1 operation (remove 2)
• c = 3: Use 1 operation (remove 3)
• c = 4: Use 2 operations (remove 2 + 2)
• c = 5: Use 2 operations (remove 2 + 3)
• c = 6: Use 2 operations (remove 3 + 3)
• c = 7: Use 3 operations (remove 2 + 2 + 3)
• c = 8: Use 3 operations (remove 2 + 3 + 3)
• c = 9: Use 3 operations (remove 3 + 3 + 3)

Notice a pattern? We're trying to use as many "remove 3" operations as possible since they're more efficient (removing more elements per operation). The key observation is that any number c ≥ 2 can be expressed as a combination of 2s and 3s:

• Numbers divisible by 3 use only 3s
• Numbers leaving remainder 1 when divided by 3 (like 4, 7, 10) use two 2s and the rest as 3s
• Numbers leaving remainder 2 when divided by 3 (like 2, 5, 8) use one 2 and the rest as 3s

This leads us to the formula ⌊(c + 2) / 3⌋:

• When c % 3 == 0: We need c / 3 operations
• When c % 3 == 1: We need (c - 4) / 3 + 2 = (c + 2) / 3 operations (replace one 3 with two 2s)
• When c % 3 == 2: We need (c - 2) / 3 + 1 = (c + 2) / 3 operations (add one 2)

The formula elegantly captures all three cases, giving us the minimum number of operations for any count c ≥ 2.

Learn more about Greedy patterns.

Solution Approach

The implementation uses a hash table (Counter in Python) to count occurrences of each element, then applies the greedy formula to calculate the minimum operations.

Step 1: Count Element Frequencies

count = Counter(nums)

We use Python's Counter to create a frequency map where keys are the unique elements and values are their occurrence counts.

Step 2: Calculate Operations for Each Unique Element

ans = 0
for c in count.values():
    if c == 1:
        return -1
    ans += (c + 2) // 3

For each frequency c in the hash table:

• If c == 1, it's impossible to remove this element, so we immediately return -1
• Otherwise, we add (c + 2) // 3 operations to our answer

The formula (c + 2) // 3 works because:

• Integer division // automatically floors the result
• Adding 2 before dividing by 3 gives us the ceiling effect for the specific pattern we need:
  • When c % 3 == 0: (c + 2) // 3 = c // 3 (exact division)
  • When c % 3 == 1: (c + 2) // 3 = (c + 2) // 3 = (c - 1) // 3 + 1 (need extra operation for remainder)
  • When c % 3 == 2: (c + 2) // 3 = (c + 2) // 3 = c // 3 + 1 (need extra operation for remainder)

Step 3: Return Total Operations

return ans

The sum of operations for all unique elements gives us the minimum total operations needed.

Time Complexity: O(n) where n is the length of the input array (for counting frequencies)
Space Complexity: O(k) where k is the number of unique elements in the array

Example Walkthrough

Let's walk through the solution with the array nums = [14, 12, 14, 14, 12, 14, 14, 12, 12, 12, 12, 14, 14, 12, 14, 14].

Step 1: Count frequencies First, we count how many times each element appears:

• Element 12 appears 7 times
• Element 14 appears 9 times

Step 2: Calculate operations for each unique element

For element 12 (appears 7 times):

• We need to remove all 7 occurrences
• Using the formula: (7 + 2) // 3 = 9 // 3 = 3 operations
• We can verify this: 7 = 3 + 2 + 2 (one "remove 3" and two "remove 2" operations)

For element 14 (appears 9 times):

• We need to remove all 9 occurrences
• Using the formula: (9 + 2) // 3 = 11 // 3 = 3 operations
• We can verify this: 9 = 3 + 3 + 3 (three "remove 3" operations)

Step 3: Sum up total operations Total operations = 3 + 3 = 6

Let's trace through the actual removals to verify:

1. Remove three 12's → Array has 4 twelves and 9 fourteens left
2. Remove two 12's → Array has 2 twelves and 9 fourteens left
3. Remove two 12's → Array has 0 twelves and 9 fourteens left
4. Remove three 14's → Array has 0 twelves and 6 fourteens left
5. Remove three 14's → Array has 0 twelves and 3 fourteens left
6. Remove three 14's → Array is empty

The array is successfully emptied in 6 operations, confirming our calculation.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because:

• Creating the Counter object requires iterating through all n elements once: O(n)
• Iterating through the values in the Counter dictionary takes O(k) time, where k is the number of unique elements, and k ≤ n
• Each operation inside the loop (checking if c == 1 and calculating (c + 2) // 3) takes O(1) time
• Overall: O(n) + O(k) = O(n)

The space complexity is O(n). This is because:

• The Counter object stores at most n key-value pairs (in the worst case where all elements are unique)
• The variable ans uses O(1) space
• Overall: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Single Occurrences

One of the most common mistakes is forgetting to check if any element appears exactly once in the array. Since we can only remove elements in groups of 2 or 3, a single occurrence makes it impossible to empty the array.

Incorrect Implementation:

def minOperations(self, nums: List[int]) -> int:
    frequency_map = Counter(nums)
    total_operations = 0
  
    for frequency in frequency_map.values():
        # Missing the check for frequency == 1
        total_operations += (frequency + 2) // 3
  
    return total_operations

Correct Implementation:

def minOperations(self, nums: List[int]) -> int:
    frequency_map = Counter(nums)
    total_operations = 0
  
    for frequency in frequency_map.values():
        if frequency == 1:  # Critical check
            return -1
        total_operations += (frequency + 2) // 3
  
    return total_operations

2. Using the Wrong Formula for Minimum Operations

Another pitfall is trying to use a different formula or complex conditional logic instead of the elegant (frequency + 2) // 3 formula.

Incorrect/Overcomplicated Implementation:

def minOperations(self, nums: List[int]) -> int:
    frequency_map = Counter(nums)
    total_operations = 0
  
    for frequency in frequency_map.values():
        if frequency == 1:
            return -1
        elif frequency % 3 == 0:
            total_operations += frequency // 3
        elif frequency % 3 == 1:
            total_operations += (frequency - 4) // 3 + 2  # Overly complex
        else:  # frequency % 3 == 2
            total_operations += frequency // 3 + 1
  
    return total_operations

Correct Implementation:

def minOperations(self, nums: List[int]) -> int:
    frequency_map = Counter(nums)
    total_operations = 0
  
    for frequency in frequency_map.values():
        if frequency == 1:
            return -1
        total_operations += (frequency + 2) // 3  # Simple, unified formula
  
    return total_operations

3. Attempting to Greedily Remove Elements Instead of Working with Frequencies

Some might try to actually simulate removing elements from the array, which is unnecessary and inefficient.

Incorrect Approach:

def minOperations(self, nums: List[int]) -> int:
    nums_copy = nums.copy()
    operations = 0
  
    while nums_copy:
        # Try to find and remove groups of 3 or 2
        # This approach is inefficient and error-prone
        # ...complex logic to actually remove elements...
  
    return operations

Correct Approach: Work with frequencies directly without modifying the array, as shown in the correct solution above.

4. Integer Division vs Float Division

Using regular division / instead of integer division // will give incorrect results.

Incorrect:

total_operations += (frequency + 2) / 3  # Returns float, not int

Correct:

total_operations += (frequency + 2) // 3  # Returns int