December 22, 2008

Finding Majority Element

Jargon: Majority Element is an element of an array that occurs more than half the number of times in the array. Also, [x] means smallest integer greater than x.

Problem 1: Assume that an integer array A[1..n] has a majority element and elements other than majority element are distinct. How to find majority element. What's the space and time complexity of the algorithm ?

Complexity: Time Complexity = n/2(comparisons), Space Complexity = O(1)

Solution: show

Problem 2: Assume that an integer array A[1..n] has a majority element and elements other than majority element need NOT be distinct. How to find majority element. What's the space and the time complexity of the algorithm?

Complexity: Time Complexity=n(comparison), Space Complexity=O(1)

Solution: show

Problem 3: Now consider that there are k majority elements, i.e., each of the k majority elements appear in the array more than ceil(n/(k+1)) times. How do we find the k majority elements. (Problem 2 is a special case of this problem with k=1).  

Complexity: Time Complexity=k*n(comparison), Space Complexity=O(k)  

Solution: show

9 comments:

  1. If there's a majority element and non-majority elements are distinct, you can solve in O(1) expected time. Just pick a random pair of distinct indexes, and see if the values at those indexes are the same. If so, you've found your majority element. The probability of making such a pick is > 1/4, so the expected number of attempts needed is < 4.

    ReplyDelete
  2. Interesting solution Eugene, but we are looking for the worst case complexity here.

    In general probabilistic methods are faster (for e.g. for primality testing) but its hard to put tight guarantees on them.

    ReplyDelete
  3. Strictly speaking, your Space Complexity is actually O(log n) (or O(k log n)) since maintaining a counter isn't O(1) space but actually O(log n) space.

    Zorba P.

    ReplyDelete
  4. Zorba,

    Please be specific about which problem you are talking about.

    For all the three problems, look at the pseudo code and think if you see the memory to be O(1) or O(K log N).

    I guess you are confusing between space and time complexities or may be iterative vs recursive implementations ?

    Please elaborate.

    Thanks.

    Which problem are you talking about

    ReplyDelete
  5. hi,

    in the third part, should the condition be if ( j<k) as every time the control breaks out of the first nested for loop it will always be less than k and move on the next for loop.

    ReplyDelete
  6. also what is the initial value of maj[] and count[] in the third part? thanks!

    ReplyDelete
  7. Thanks Anon, you are right about the comparison (j > k). It has been corrected.

    For initialization, maj[i] = Nan, count[i] = 0 should work.

    ReplyDelete