⚡Flashcard Drill➔
NeetCode #145LC-2870MediumArrays & Hashing
← Back to All Problems

#145 · #2870 · Minimum Number of Operations to Make Array Empty(使数组为空的最少操作次数)

📌 Problem Statement & Constraints

You are given an array nums of positive integers. In one operation, remove either two equal elements or three equal elements. Return the minimum number of operations to empty the array, or -1 if it is impossible. Constraints: 2 <= nums.length <= 10^5, 1 <= nums[i] <= 10^6.

💡 Core Algorithmic Approaches

  1. The answer is a sum over each distinct value, since operations never mix different values.
  2. For a frequency c, the minimum number of operations is c // 3 plus 1 if c % 3 != 0, i.e. ceil(c / 3) adjusted: use as many triples as possible, then handle the remainder with a pair.
  3. The only impossible case is c == 1, since a single element cannot be removed by either operation.
  4. Verify the formula: c = 2 -> 1, c = 4 -> 2 (2+2), c = 5 -> 2 (3+2), c = 7 -> 3 (3+2+2), c = 8 -> 3 (3+3+2).

💻 Benchmark Python3 Implementation

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        from collections import Counter
        res = 0
        for c in Counter(nums).values():
            if c == 1:                     # impossible
                return -1
            res += c // 3
            if c % 3:
                res += 1                   # handle the remainder with a pair
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to count and a constant-size scan over the distinct values.
💾 Space Complexity
O(k) for the counter.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the c == 1 check: a single occurrence can never be removed, so the answer is -1.
  • Using ceil(c / 3) alone: for c = 4 this gives 2, which is correct, but for c = 2 it gives 1 -- also correct. The formula c // 3 + (1 if c % 3 else 0) matches ceil(c / 3) for c >= 2 and is the cleanest way to express it.
  • Using c // 2: removing pairs only is not optimal; triples are more efficient.
  • Aggregating over the whole array instead of per distinct value: operations only work within one value, so the counts must be handled separately.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems