Find all values repeating more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time

Question

Given a parameter $k$ and an array (not sorted) of length $n$ return all values which repeat more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time.

I've managed this in $O(nk)$ time, but can't figure out how to do it in the required performance.

Answer 1

The Misra-Gries summary is a simple technique which will find, for a given $k$, all elements in a sequence of $n$ elements which occur more than $\lfloor n/k \rfloor$ times, introduced in the 1982 paper Finding Repeated Elements as a generalization of the more well-known Boyer-Moore majority vote algorithm, which is essentially the case where $k = 2$.

The Misra-Gries summary can be computed in $O(n\log k)$ time and $O(k)$ space with a single scan of the sequence. However, it always returns $k-1$ distinct values without any guarantee that any of them satisfy the criterion; it only guarantees that if a value satisfies the criterion, it will appear in the list. Reducing the summary to the required values requires a second scan of the sequence to count the occurrences of each candidate value. This scan can be performed in $O(n \log k)$ time by the simple expedient of putting the $k$ values into an associative array implemented with a balanced binary search tree, such as a red-black tree.

In fact, constructing the BST for the second scan is not really necessary because the $O(n \log k)$ Misra-Gries computation actually produces such a tree. The computation can be performed as follows:

1. Initialise an empty associative array $\mathit{C}$ which maps sequence elements onto non-negative integers. The array will have a fixed capacity of $k$ elements, but may contain empty slots.

2. For each element $a$ from the sequence in turn:

   1. Precondition: $C$ contains at most $k-1$ pairs.

   2. If $a\text{ is in }C$, increment its associated value.

   3. Otherwise, add $\langle a, 1\rangle$ to $C$.

   4. If $C$ now has $k$ pairs, decrement all of the associated values and remove all keys whose associated value is $0$. [Note 1]

   5. Postcondition: $C$ contains at most $k-1$ pairs.

3. At the end of the scan, $C$ contains at most $k-1$ pairs with distinct keys, which include all elements which appear in the sequence more than $\lfloor n/k \rfloor$ times.

The proof of the postcondition is simple: If step 2 was performed, the size of $C$ was not changed, so it is still at most $k-1$ because of the precondition. Otherwise, step 3 is performed, after which $C$ contains at most $k$ because step 3 adds exactly one pair to $C$. If step 4 is performed, there must be at least one pair whose associated value is $0$ and will be deleted from $C$, because step 4 can only be performed if step 3 was performed and step 3 adds a pair with associated value $1$ to $C$.

The intuitive explanation of why any element repeated more than $\lfloor n/k \rfloor$ times must be in $C$ at the end of the scan is explained by @YuvalFilmus in this related question.

The fact that the scan takes $O(n \log k)$ time can be seen from a simple amortised time analysis of the iteration. Every element from the sequence will be added to $C$ exactly once, either in step 2 or step 3, each of which take $O(\log k)$ since $C$ has at most $k$ pairs. Furthermore, each element (except for the $k-1$ final candidates) will be decremented exactly once in some occurrence of step 4. (Step 4 decrements $k$ values, but each decrement pertains to a different element of the original sequence, so the total number of decrements is $O(n)$. Another way to look at this is to observe that step 4 can be performed no more than $\lfloor n / k\rfloor$ times.)

Each decrement in step 4 consumes $O(1)$ time, but at least one pair must be deleted from $C$, which requires $O(\log k)$ time. Again, we rely on amortised analysis to see that the total number of deletions is $O(n)$.

---

In practice, this algorthm will usually be implemented with a hash table rather than a balanced binary tree. The hash table implementation replaces the guaranteed $O(\log k)$ steps with expected $O(1)$ (but worst case $O(k)$). Since the worst case is extremely unlikely, the hash table algorithm is generally cited as linear-time, although strictly speaking it is linear expected time.

---

Notes

1. As an optimisation, it's possible (and, I believe, common) to avoid adding and removing $a$ in a single iteration. It is also unnecessary to remove pairs which have been decremented to 0 provided you can find such a pair in $O(1)$ for step 2. This can be done with a bit of bookkeeping. You can also implement "decrease all counts by one" by using a base value (so that the values are the stored value minus the base value) and incrementing it by one to effectively decrement all counts. All that will change the iteration step from amortized $O(1)$ to guaranteed $O(1)$ but the extra bookkeeping is likely to result in a slower total execution time.