Range majority in constant time and linear space

Given an array A of size n, we consider the problem of answering range majority queries: given a query range [ i. . j ] where 1 ⩽ i ⩽ j ⩽ n, return the majority element of the subarray A [ i. . 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 [ i. . j ], return all the elements in the subarray A [ i. . j ] with frequency greater than α ( 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 ( 1 α ) time using O ( n lg ( 1 α + 1 ) ) space, for any fixed α ∈ ( 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.

Authors

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

Keywords

No keywords are indexed for this paper.