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
- The answer is a sum over each distinct value, since operations never mix different values.
- For a frequency
c, the minimum number of operations isc // 3plus 1 ifc % 3 != 0, i.e.ceil(c / 3)adjusted: use as many triples as possible, then handle the remainder with a pair. - The only impossible case is
c == 1, since a single element cannot be removed by either operation. - 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 == 1check: a single occurrence can never be removed, so the answer is-1. - Using
ceil(c / 3)alone: forc = 4this gives 2, which is correct, but forc = 2it gives 1 -- also correct. The formulac // 3 + (1 if c % 3 else 0)matchesceil(c / 3)forc >= 2and 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.