Range Majority Query | Algorithms Notes
Given an array A of n numbers, design an algorithm to support a query of given a range A[l, r], find the majority of A[l, r].
Solution:
Without loss of generality, we assume that the range of A is [1..m]. Since the majority of A[l, r] must be the median of A[l, r] as well. The problem becomes to verify whether the median of A[l, r] has a frequency higher than (l–r)/2 in A[l, r]. This can be done easily by maintain a sorted array for each j in [1..m], storing all indices i such that A[i] = j. The complexity is the same as range median finding.
http://cs.stackexchange.com/questions/16671/range-majority-queries-most-freqent-element-in-range
Given an array A of n numbers, design an algorithm to support a query of given a range A[l, r], find the majority of A[l, r].
Solution:
Without loss of generality, we assume that the range of A is [1..m]. Since the majority of A[l, r] must be the median of A[l, r] as well. The problem becomes to verify whether the median of A[l, r] has a frequency higher than (l–r)/2 in A[l, r]. This can be done easily by maintain a sorted array for each j in [1..m], storing all indices i such that A[i] = j. The complexity is the same as range median finding.
http://cs.stackexchange.com/questions/16671/range-majority-queries-most-freqent-element-in-range
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.
Read full article from Range Majority Query | Algorithms Notes