Linear-Space Data Structures for Range Mode Query in Arrays

Stephane Durocher, Jason Morrison

A mode of a multiset $S$ is an element $a\in S$ of maximum multiplicity; that is, $a$ occurs at least as frequently as any other element in $S$. Given a list $A[1:n]$ of $n$ items…