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.
1
$\begingroup$
$\endgroup$
-
1$\begingroup$ What have you tried already? What is blocking you? What is wrong with existing solutions? lmgtfy.com/?q="range+majority" $\endgroup$ – jbapple Nov 3 '13 at 17:30
3
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ Yes, items are not in sorted order. In fact, space for time trade is what I would like to do. Could you please explain how it should be done? I couldn't understand all this very complex solutions that are in academic papers found in the internet. There is one more thing, preprocessing time cannot be longer than O(N*M) nor O(N^2) . Thank you for your concern! $\endgroup$ – alexd Nov 3 '13 at 18:39
-
2$\begingroup$ I am afraid this can not be explained in a tiny amount of space :-( You should really download and read the following paper: S. Durocher, M. He, I Munro, P.K. Nicholson, M. Skala, Range majority in constant time and linear space, Information and Computation 222 (2013) 169–179, Elsevier. $\endgroup$ – Massimo Cafaro Nov 3 '13 at 19:50
