Minimum Number of Operations to Make Array Empty
- 1 min read
- Array
- LC-Medium
3 years ago
My Solution
- Basically, make a heap out of all frequencies, and each time, pop from heap, decrement by either 3 or 2, and then put back into heap
def minOperations(self, nums: List[int]) -> int:
num_operations = 0
current_size = len(nums)
counts = [(-freq, num) for num, freq in Counter(nums).items()]
heapify(counts)
while counts:
freq, num = heappop(counts)
freq *= -1
if freq == 1: return -1
if freq % 3 == 0: freq -= 3
elif freq % 2 == 0: freq -= 2
else: freq -= 3
num_operations += 1
if freq:
heappush(counts, (-freq, num))
return num_operations
Optimal Solution
- Basically the same as above, but instead no heap is used, because the order doesn't matter here at all.
- Plus, the bottom solution basically achieves the same thing as the top, only difference is that it does it all in one go because
ceil(freq / 3)captures both 2-decrement and 3-decrement events
💀💀
def minOperations(self, nums: List[int]) -> int:
num_operations = 0
for freq in Counter(nums).values():
if freq == 1:
return -1
num_operations += ceil(freq / 3)
return num_operations