1
$\begingroup$

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.

$\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$

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.

$\endgroup$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.