We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Operations to Make Array Empty

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each element's count must be either zero or a multiple of two or three to be removable.
  • To minimize operations, prioritize removing groups of three when possible, as they reduce the count faster.
  • If there are leftover items after maximizing removals of threes, pairs can be used, but if there are unremovable items, return -1.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution involves counting the occurrences of each number using a hash table (dictionary). For each unique number, we calculate how many operations are needed to remove all occurrences based on the count:

  1. If the count is a multiple of three, remove as many groups of three as possible.
  2. If there are leftover items that cannot form a pair or a group of three, it's impossible to empty the array, so return -1.
  3. Sum the total operations required for all unique numbers.

Code Solutions

def min_operations(nums):
    from collections import Counter
    
    count = Counter(nums)
    operations = 0
    
    for num, freq in count.items():
        if freq == 1:
            return -1  # Can't remove a single element
        elif freq % 3 == 0:
            operations += freq // 3
        elif freq % 3 == 1:
            if freq < 3:
                return -1  # Can't form a pair or triplet
            operations += (freq // 3) + 1  # One extra operation for the leftover
        else:  # freq % 3 == 2
            operations += freq // 3 + 1  # One extra operation for the pair
            
    return operations
← Back to All Questions