An array of length

nhaskdistinct elements, \(k \lt n\). Find the most repeated value in the array.

(note that this isn't the same as finding the majority (if there is one) in an array which can be done in \(\Theta(n)\) by finding the median or using the more simplistic Boyer-Moore Majority Vote Algorithm)

The straight forward solution gives us \(\Theta(n\lg{n})\), by sorting the array and doing a linear pass while maintaining the maximum pair of (value, number of repeats).

We can slightly improve this to \(\Theta(n\lg{k})\) by using \(O(k)\) memory.

Build a Red-Black tree of all distinct values in the array. There are *k* of
those, so insertion takes \(O(\lg{k})\). In every node, store the number of times
its key has appeared in a field, call it *size*.

We build the tree by going over the input array and inserting each value. If
a value is already in the tree, we simply increment its *size* by 1.

Like before, we keep a pair of (value, size) for the most repeated value that
is currently in the tree. Update this pair as necessary when inserting into the
tree (by examining the *size* of the inserted node).

We have *n* values to insert to a tree with *k* nodes which gives us a total
running time of \(\Theta(n\lg{k})\).