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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityGiven 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.
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.