Linear-Space Data Structures for Range Mode Query in Arrays

Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison & Bryan T. Wilkinson
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 an array A[1:n] of n elements, we consider a basic problem: constructing a static data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices (i, j) for which a mode of A[i:j] must be returned. The...