Range majority in constant time and linear space

Stephane Durocher, Meng He, J. Ian Munro, Patrick K. Nicholson, Matthew Skala

Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review


Given an array $A$ of size $n$, we consider the problem of answering range majority queries: given a query range $[ildots j]$ where $1le ile jle n$, return the majority element of the subarray $A[ildots j]$ if it exists. We describe a linear space data structure that answers range majority queries in constant time. We further generalize this problem by defining range $-majority queries: given a query range $[ildots j]$, return all the elements in the subarray $A[ildots j]$ with frequency greater than $alpha (j−i+1)$. We prove an upper bound on the number of $-majorities that can exist in a subarray, assuming that query ranges are restricted to be larger than a given threshold. Using this upper bound, we generalize our range majority data structure to answer range $-majority queries in $O(1alpha)$ time using $O(n lg (1alpha+1))$ space, for any fixed $alphain (0,1)$. This result is interesting since other similar range query problems based on frequency have nearly logarithmic lower bounds on query time when restricted to linear space.
TidsskriftInformation and Computation
Udgave nummerJanuary 2013
Sider (fra-til)169-179
Antal sider11
StatusUdgivet - 2013
Udgivet eksterntJa


Dyk ned i forskningsemnerne om 'Range majority in constant time and linear space'. Sammen danner de et unikt fingeraftryk.