# 4.01.2024 [2870. Minimum Number of Operations to Make Array Empty]
Minimum pairs or triples duplicate removal operations to empty array of numbers.
4.01.2024
2870. Minimum Number of Operations to Make Array Empty medium
blog post
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 check 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 repeats 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
}}