LeetCode Entry
2870. Minimum Number of Operations to Make Array Empty
Minimum pairs or triples duplicate removal operations to empty array of numbers.
2870. Minimum Number of Operations to Make Array Empty medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/461
Problem TLDR
Minimum pairs or triples duplicate removal operations to empty array of numbers.
Intuition
The first idea, is to count each kind of number. Then we must analyze each frequency: the number of removal operations ops will be the same for each f, so we can write a Dynamic Programming recurrent formula: ops(f) = 1 + min(ops(f - 2), ops(f - 3)). This is an accepted solution.
Then, we can think about other ways to optimally split f into a sum of a*2 + b*3: we must maximize b and minimize a. To do that, let’s prioritize f % 3 == 0 check. Our checks will be in this order:
f % 3 == 0 -> f / 3
(f - 2) % 3 == 0 -> 1 + f / 2
((f - 2) - 2) % 3 == 0 -> 1 + f / 2
... and so on
However, we can spot that recurrence repeat itself like this: f, f - 2, f - 4, f - 6, .... As 6 is also divisible by 3, there are total three checks needed: f % 3, (f - 2) % 3 and (f - 4) % 3.
Approach
Write the recurrent DFS function, then add a HashMap cache, then optimize everything out. Use the Kotlin’s API:
- groupBy
- mapValues
- sumOf
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun minOperations(nums: IntArray) = nums
.groupBy { it }.mapValues { it.value.size }.values
.sumOf { f -> when {
f < 2 -> return -1
f % 3 == 0 -> f / 3
(f - 2) % 3 == 0 || (f - 4) % 3 == 0 -> 1 + f / 3
else -> return -1
}}