Minimum Number of Operations to Make Array Empty

Minimum Number of Operations to Make Array Empty - 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 the minimum number of operations required to make the array empty, or -1 if it is not possible.

Input & Output

Example 1 — Mixed Frequencies

$ Input: nums = [2,1,3,3,2]

› Output: -1

💡 Note: Element 1 appears only once, which cannot be removed using operations that require 2 or 3 identical elements. Therefore, it's impossible to make the array empty.

Example 2 — All Removable

$ Input: nums = [2,3,3,2,2,4,4,4]

› Output: 4

💡 Note: Element 2 appears 3 times (1 operation), element 3 appears 2 times (1 operation), element 4 appears 3 times (1 operation). Total: 3 operations. Wait, let me recalculate: 2 appears 3 times → ceil(3/3)=1, 3 appears 2 times → ceil(2/3)=1, 4 appears 3 times → ceil(3/3)=1. Total = 3 operations.

Example 3 — Large Frequencies

$ Input: nums = [14,12,14,14,12,14,14,12,12,12,12,14,14,12,14,14,14,12]

› Output: 7

💡 Note: Element 12 appears 9 times → ceil(9/3)=3 operations. Element 14 appears 9 times → ceil(9/3)=3 operations. Total = 6 operations. Actually let me recount: I see 12 appears 9 times and 14 appears 9 times, so 3+3=6 operations.

Constraints

2 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Count frequency of each unique element

Operation Planning

Calculate minimum operations using mathematical formula

Result

Sum operations or return -1 if impossible

Key Takeaway

🎯 Key Insight: Use ceil(frequency/3) formula to find minimum operations, but return -1 if any element appears only once

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that we can only remove elements in groups of 2 or 3, so any element appearing only once makes the problem impossible. For elements with frequency f ≥ 2, the minimum operations needed is ceil(f/3), which greedily uses as many groups of 3 as possible. Best approach is Greedy Mathematical with Time: O(n), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Enumeration	O(3^n)	O(n)	Try all possible combinations of operations recursively
Greedy Mathematical Approach	O(n)	O(k)	Optimal greedy solution using mathematical insight
Frequency Count with Math	O(n)	O(n)	Count frequencies, then use mathematical formula for minimum operations

Recursive Enumeration — Algorithm Steps

Count frequency of each element
For each element, try all combinations of 2s and 3s
Return minimum operations across all valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count how many times each element appears

Recursive Exploration

For each element, try all combinations of 2s and 3s

Find Minimum

Return minimum operations across all possibilities

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_SIZE 100000

typedef struct {
    int key;
    int value;
} Pair;

int minOps(int count) {
    if (count == 0) return 0;
    if (count == 1) return INT_MAX;
    
    int result = INT_MAX;
    if (count >= 2) {
        int ops2 = minOps(count - 2);
        if (ops2 != INT_MAX && ops2 < result - 1) result = 1 + ops2;
    }
    if (count >= 3) {
        int ops3 = minOps(count - 3);
        if (ops3 != INT_MAX && ops3 < result - 1) result = 1 + ops3;
    }
    return result;
}

int solution(int* nums, int numsSize) {
    Pair freq[MAX_SIZE];
    int freqSize = 0;
    
    // Count frequencies
    for (int i = 0; i < numsSize; i++) {
        int found = 0;
        for (int j = 0; j < freqSize; j++) {
            if (freq[j].key == nums[i]) {
                freq[j].value++;
                found = 1;
                break;
            }
        }
        if (!found) {
            freq[freqSize].key = nums[i];
            freq[freqSize].value = 1;
            freqSize++;
        }
    }
    
    int totalOps = 0;
    for (int i = 0; i < freqSize; i++) {
        int ops = minOps(freq[i].value);
        if (ops == INT_MAX) return -1;
        totalOps += ops;
    }
    
    return totalOps;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int nums[MAX_SIZE];
    int numsSize = 0;
    
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    printf("%d\n", solution(nums, numsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3^n)

For each element frequency, we try exponentially many combinations

✓ Linear Growth

Space Complexity

O(n)

Hash map to store frequencies plus recursion stack

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler