Aug 082012
 

An integer x in array arr of n elements is the majority element if and only if x appears more than n/2 times in A.

 - If n is odd then it should appear at least (n+1)/2 times
 - If n is even then it should appear at least (n/2) + 1 times

Array: 1 2 3 1 2 1 1         Majority Element: 1
Array: 1 2 3 1 2 1           Majority Element: NONE (1 appears only n/2 times)
i.e Majority element is the Most frequent element in Array. But, Most frequent element of array may not be the majority element.

Write Code to print the majority element (if exists) of an Array.

Brute-Force Method:

Compare all the elements and keep counter for how many times each element is repeated.

This algorithm will take O(n2) time in the worst case.

If range of elements is very small, then a separate array to store counts can be used and hence it will take O(n) time and some extra space. But this is not applicable as a general solution when elements are random (because the count array may become very huge).

Sort the array and then count:

This will take O(n.lg(n)) time, which is the time taken to sort the array (Comparison Sorting Algorithm – when nothing is known about the rage of values in it).

If majority element exists in a sorted array, then the middle element has to be majority element itself and it must be same as either the first element or the last element (depending on whether the first half has majority element or the second half). For example, In the below picture there is no majority element (blue elements are all equal and gray ones are different).

The sufficient check to see if a majority element exist in a sorted array or not is :

    if(n%2 == 0)    // Array has EVEN No. of Elements
    {
        int firstMiddle = n/2-1, secondMiddle = n/2;

        if(arr[secondMiddle] == arr[0] || arr[firstMiddle] == arr[n-1])
             printf("MAJORITY ELEMENT EXIST");
        else
             printf("DOES NOT EXIST");
    }
    else             // Array has EVEN No. of Elements
    {
        if(arr[n/2] == arr[0] || arr[n/2] == arr[n-1])
             printf("MAJORITY ELEMENT EXIST");
        else
             printf("DOES NOT EXIST");
    }

Using Binary Search Tree:

This is just an extension to the previous (sorting) method. It will also take O(n.lg(n)) time.

1. Modify the Node struct to hold the count also along with the data and pointers.
2. Create a Binary search Tree and for duplicate values, increment the count of the node, 
   rather than allocating new node.
3. Traverse the tree and check whether count value of any node is > n/2.
   If yes, value in the node is the majority element. Else, majority element does not exist.

Find the Median:

This will take O(n) time, but has a huge constant factor.

Using Moore’s Algorithm:

Observations: If we cancel out ONE majority element with ONE other element (non-majority). Then at the end we will be left will the majority element (because more than half of the elements are majority element).

The above observation is called “Moore’s Voting Algorithm” and it will give us a candidate for Majority element. Then we just need to check whether the candidate is actually a majority element (its count is > n/2 or not).

Lets us write the two functions:

    1. To get the candidate
    2. To check if the candidate is actually the majority element.
/** Will return an element which is the only candidate for majority element 
 * If, Majority element exists, it will return Majority element
 * Else, will return some frequently occurring element
 */
int candidate(int *arr, int n)
{
    int majorityIdx = 0, count = 1;

    for(int i=1; i<n; i++)
    {
        if(arr[majorityIdx] == arr[i])
            count++;
        else
            count--;

        if(count == 0)
        {
            majorityIdx = i;
            count = 1;
        }
    }
    return arr[majorityIdx];
}

/** Function to print the majority element.
 *
 *  Will call the candidate function and then check if the candidate returned
 *  is actually a majority element or not.
 */
void majority(int *arr, int n)
{
    int c = candidate(arr, n);

    int count = 0;
    for (int i=0; i<n; i++)
        if(arr[i] == c)
            count++;

    if (count > n/2)
        printf("Majority Element = %d", c);
    else
        printf("No Majority Element.");
}

Time Complexity: O(n)
Extra Space: O(1)

  4 Responses to “Majority Element of an Array (Moore’s Algorithm)”

Comments (4)
  1. Sorted array like int[] arr = { 1,1,2,2,2,2,3}; first solution will not work.
    Both conditions will be failed if(arr[n/2] == arr[0] || arr[n/2] == arr[n-1])
    But array is valid and majority element(2) exist.

  2. (line 16)

  3. In the Moore’s Algorithm will work, if you’ll change from “if (count==0)” to “if (count <=0)".

    • I think the check is fine.. Look at the definition of Majority element.. If a number appears exactly n/2 times then it is not majority.. It has to come more than n/2 times.. count becomes ==0 when we find other number equal to times this number is repeated. We should leave it there itself..

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)