[Solved]: Range majority queries - most freqent element in range

Problem Detail: 

Given N numbers and M range queries (starting and ending points), I need to compute majority (most frequent element, if it exists) in these ranges.

I'm looking for an algorithm that would answer queries in logarithmic or even constant time.

Asked By : alexd

Answered By : Massimo Cafaro

If the $N$ items are in ascending sorted order and stored into an array, you can determine a majority candidate in $O(1)$ time for a specified range by returning the item whose index is the range median. Therefore, this will require $O(M)$ time in the worst case for $M$ range queries. Note that the item returned in each query is a candidate: you need to verify if the item actually is a majority element in the range. And, verification is linear in the number of items in the range.

EDIT: explained tradeoff between space and time

If the items are not in sorted order, than finding a candidate element requires in the worst case time linear in the number of items in the range, using the Boyer-Moore algorithm and constant space (one counter). You can not determine a candidate element in time logarithmic in the number of items in the range while using constant space. However, if you trade space for time, you can determine a majority element in $O(1)$ time at the cost of using linear space.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16671

 Ask a Question

 Download Related Notes/Documents