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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Operations to Make Array Empty

Number: 3094

Difficulty: Medium

Paid? No

Companies: Amazon, Apple

Problem Description

Given a 0-indexed array of positive integers, you are allowed to repeatedly perform two types of operations:

  • Delete two elements with equal values.
  • Delete three elements with equal values.

Determine the minimum number of operations required to empty the array. If it is impossible to empty the array, return -1.

Key Insights

  • The problem can be broken down by processing each unique number and its frequency.
  • If any unique number appears only once, it is impossible to remove it (must appear at least twice).
  • Use a greedy approach: try to remove groups of three as much as possible since a group of three counts as one operation.
  • Handle leftover counts carefully. For counts with remainder 1 (i.e. count ≡ 1 mod 3), it’s often beneficial to “convert” one triple removal into two pair removals.
  • Use mathematical formulas to compute the minimum operations for each frequency count.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the array (plus O(unique numbers) processing). Space Complexity: O(n) in the worst-case to store the frequency count of elements.

Solution

We first count the frequency of each number in the array. For each unique number with count c:

  • If c == 1, it's impossible to remove that element, so return -1.
  • If c % 3 == 0, we can delete the elements in c/3 operations (using only triple removals).
  • If c % 3 == 1 (and c >= 4), we remove one triple removal from the optimal triple grouping (i.e. treat 4 elements as two pairs) leading to (c - 4) / 3 triple removals plus 2 pair removals.
  • If c % 3 == 2, we can perform c // 3 triple removals plus one additional pair removal.

Sum the operations over all unique numbers to get the total minimum operations.

Code Solutions

# Python solution
from collections import Counter

def minimumOperations(nums):
    # Count frequency of each element
    counts = Counter(nums)
    operations = 0
    
    # Process each unique number and its frequency
    for num, cnt in counts.items():
        if cnt == 1:
            # If a number appears only once, it's impossible to remove it
            return -1
        
        # When frequency is exactly divisible by 3, use triple removals
        if cnt % 3 == 0:
            operations += cnt // 3
        # For remainder 1, we need to adjust: remove one triple and use two pairs
        elif cnt % 3 == 1:
            # A valid scenario must have at least 4 occurrences
            if cnt < 4:
                return -1
            operations += (cnt - 4) // 3 + 2
        # For remainder 2, add one pair removal to the triple removals
        elif cnt % 3 == 2:
            operations += cnt // 3 + 1
    
    return operations

# Example usage:
nums1 = [2,3,3,2,2,4,2,3,4]
print(minimumOperations(nums1))  # Expected output: 4

nums2 = [2,1,2,2,3,3]
print(minimumOperations(nums2))  # Expected output: -1
← Back to All Questions