Leetcode 2870 explainer (for Recurse Center)

lc_2870_explainer.md

class Solution:

    def minOperations(self, nums: List[int]) -> int:

        def opMin(freq: int) -> int:
            assert freq > 1, f"{opMin.__name__} only takes freq > 1"
            call_stack = [(freq, 0)]
            while call_stack:
                k, ops = call_stack.pop()
                if k < 0:
                    continue
                if k == 0:
                    return ops
                call_stack.append((k - 2, ops + 1))
                call_stack.append((k - 3, ops + 1))

        freqs = Counter(nums)
        if any((v == 1 for v in freqs.values())):
            return -1
        ops = 0
        for freq in freqs.values():
            ops += opMin(freq)
        return ops

FWIW, here's how I wrote the DFS, @Jacob Vartuli-Schonberg (he) (F2'20) -- your idea of favoring the $3$ -side of the tree is great!

We can actually just bail early from the search once we have a number of operations that works (reduces freq to $0$). This is because the first number of operations that works when recursively exploring the $3$ -side of the tree will necessarily be the way that maximizes the number of "delete three" operations.

Without this, the tree has $O(L)$ levels (where $L$ is the largest frequency in our array), and we make two choices at each level, so $O(2^L)$ work overall (since the non-recursive work is constant). BUT, we get the benefit of pruning, so our search is really doing $O(L)$ work because we are taking as many $3$ s as we can: we go as far down left of the tree until we can, then going right as much as we need to, which is limited to at most two right choices since $4$ is the largest even integer modulo $6$. Yes, we do explore near the end potentially a few extra nodes, but that's easily limited to $O(1)$ (e.g., $k = 5$ we try taking two $3$ s out (❌) before trying $3$ and $2$ (✅).

So for every number frequency, it takes us $O(L)$ work to find the minimum number of operations. How many frequencies do we have?

I claim there are $O(\sqrt{n})$ frequencies over an array of $n$ numbers in the worst of cases. A worst case is when we have the maximal number of frequencies; so for a big $L$, we would have something like [2, 2, 3, 3, 3, 4, 4, 4, 4, ..., L ..., L] (i.e., the last $L$ numbers are $L$). This would mean there are $$n = \underbrace{2 + 3 + ... + L}_{O(L) \text{ distinct frequencies}}$$ numbers in the array, so $$L = O(\sqrt{n})$$.

Now, we know $L = O(\sqrt{n})$, so we get a $O(L \cdot L) = O(\sqrt{n}\ \cdot \sqrt{n}) = O(n)$ runtime overall.