Link: https://leetcode.com/problems/minimum-number-of-operations-to-make-array-empty/
Solution:
DSA: hash map
Intuition
Since we are permitted to remove two or three duplicate elements from any indices, frequency map comes to mind. Notice that a unique element can never be removed because the rules only allow removal by 2’s and 3’s…this would mean that its not possible to make the array empty and we return -1.
As long as the count is greater than 1, it can be made empty with a combination of 2 deletions and 3 deletions. We are concerned with the minimum though, which means that we must use the 3 deletion rule as many times as possible. How?
Lets say we have So lets say we have 7 3's
, the optimal number of deletions is 3. First delete 3 3's
, then delete 2 3's
and then 2 3's
again. The idea is to greedily use 3 deletions, and if we are left with 1, then we a deletion, because we replace the last 3 deletion with a 2 deletion.
For example:
[3, 3, 3, 3, 3, 3, 3] no deletions
[3, 3, 3, 3] three deletion
[3] three deletion...one remains so we add a deletion.
why? because conceptually, adding the deletion is the same as using 2 two deletions instead of 1 three deletion.
[3, 3, 3, 3, 3, 3, 3] no deletions
[3, 3, 3, 3] three deletion
[3, 3] two deletion
[] two deletion
Of course, since we only have a count we can perform this process mathematically with a simple trick.
Implementation
Visual
Review 1
Using ceil(count/3)
is very clever here. I was thinking to add an extra operation if count % 3 == 1
…which works but ceil
does the job more elegantly.