Range majority in constant time and linear space

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

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

Abstract

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.
Original languageEnglish
JournalInformation and Computation
Volume222
Issue numberJanuary 2013
Pages (from-to)169-179
Number of pages11
ISSN0890-5401
Publication statusPublished - 2013
Externally publishedYes

Fingerprint

Dive into the research topics of 'Range majority in constant time and linear space'. Together they form a unique fingerprint.

Cite this