Majority Element in an array

Tushti -

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

In this article, we have discussed algorithmic techniques to find the majority element in an array. The brute force algorithm takes O(N2) time while the most efficient algorithm can do it in O(N) time.

Table of contents:

  1. Problem statement: Majority Element in an array
  2. Naive technique
  3. Sorting the array
  4. Using a Hashmap
  5. Using Binary Search Tree

We have earlier discussed Boyer Moore Algorithm to find the Majority element in an array.

Summary of different approaches:

Approach Time Complexity Space Complexity
Naive technique O(N2) O(1)
Sorting the array O(N logN) O(1)
Using a Hashmap O(N) O(N)
Using Binary Search Tree O(N logN) O(N)
Boyer Moore Algorithm O(N) O(1)

Problem statement: Majority Element in an array

Majority element is an element in an array whose frequency more than or equal to N/2 where N is the total number of elements in the array. This means if there are N elements, we need to find the element that occurs at least N/2 times.

Example:
Input :{1,2,2,2,2,3,5}
Output : 2
Explanation : 2 is the majority element as it occurs more than 7/2 or 3 times.

Input :{1,2,4,3,5}
Output : -1
Explanation : no majority element exists

1. Naive technique

The idea is to count the occurences of each element in the array by runnning two loops. If the count exceeds n/2, we immediately return the element.

Code

Implementation in Java:

public int majorityElement(int arr[], int n)
{
    for(int i=0;i<n;i++)
    {
        int count = 0;
        for(int j=i+1;j<n;j++)
        {
            if(arr[j] == arr[i])
                count++:
            if(count > n/2)
                return arr[j];
        }
    }
    return -1;
}

Time complexity

This approach takes O(N^2) time.

This is evident because for each element we traverse all the elements on it's right, which is upperbound by O(N). Hence, the time complexity becomes O(N^2).

Space complexity

Space complexity is O(1) as no auxiliary space is used.

2. Sorting the array

In this approach, we sort the array first. Once done, we keep a count on the number of occurences of each element. This is done by incrementing a variable 'count' (initially set to 0) whenever arr[i] is equal to arr[i+1].

The idea is to make use of the fact that after sorting, elements with the same value are together one after the other. Let'd take a look at an example dry run and the code to get a better understanding of the algorithm.

Code

Implementation in Java:

public static int majorityElement(int arr[], int n)
{
    int count = 0;
    for(int i=0;i<n-1;i++)
    {
        if(arr[i] == arr[i+1])
        {
            count++;
        }
        else
        {
            if(count > n/2)
            return arr[i];
            else
            count = 0;
        }
    }
    return -1;
}

Time complexity

Sorting takes O(N * logN) time. Traversing the array takes O(N) time.

Total time is O(N * logN) + O(N) = O(N * logN)

Space complexity

Space complexity is O(1) because auxiliary space is used.

3. Using a Hashmap

We will be using a hashmap to keep track of the frequency of the elemnts of the array. We increment the count of the element in the hashmap. If the count becomes greater than n/2, return that element as the majority element.

Algorithm

  1. Create a Hashmap/set.
  2. Insert elements in the hashmap an update their frequency.
  3. If the frequency becomes greater than n/2, return the element.

Code

Implementation in Java:

public static int majorityElement(int arr[], int n)
{
    HashMap<Integer, Integer> map = new HashMap<>();

    for(int i=0;i<n;i++)
    {
        if(map.containsKey(arr[i]))
        {
            map.put(arr[i], map.get(arr[i]) + 1);

            if(map.get(arr[i]) > n/2)
                return arr[i];
        }
        else
        {
            map.put(arr[i],1);
        }
    }
    return -1;
}

Example: Dry Run

Given arr[] = {2,5,1,2,3,2,2}, N = 7
Let's create a hashmap that stores the frequency of each element = []
Now, we start traversing the array:

  • i = 0: Add element (arr[0] = 2) to the hashmap = [['2': 1]]
  • i = 1: Add element (arr[1] = 5) to the hashmap = [['2': 1],['5': 1]]
  • i = 2: Add element (arr[2] = 1) to the hashmap = [['2': 1],['5': 1],['1': 1]]
  • i = 3: Increment frequency of arr[3] = 2, hashmap = [['2': 2],['5': 1],['1': 1]]
  • i = 4: Add element (arr[4] = 3) to the hashmap = [['2': 2],['5': 1],['1': 1],['3': 1]]
  • i = 5: Increment frequency of arr[5] = 2, hashmap = [['2': 3],['5': 1],['1': 1],['3': 1]]
  • i = 6: Increment frequency of arr[6] = 2, hashmap = [['2': 4],['5': 1],['1': 1],['3': 1]]

Now traverse the hashmap and return the element with the highest frequency, that is element '2' with frequency 4.

Time complexity

The array is traversed only once. The time complexity is O(N).

Space complexity

The hashmap/set uses O(N) extra space, hence space complexity is O(N).

4. Using Binary Search Tree

This technique involves changing the node structure of the tree. A new data member is added to the node structure which keeps track of the count of the element. The new node structure is this:

New node structure

class Node
{
        int data;
        int count;
        Node left, right;

        Node(int d)
        {
            data = d;
            left = null;
            right = null;
            count = 0;
        }
}

Algorithm

  1. Insert the element as a node in the BST.
  2. If a node already exists, increase it's count.
  3. If a node does not exist for the element, create a new node and insert it at the correct position in the BST.
  4. Perform an inorder traversal. If count exceeds n/2, return the element as majority element.

Code

Implementation in Java:

public static Node inorder(Node root)
{
   if(root == null)
   return null;

   inorder(root.left);
   if(root.count > n/2)
   return root;
   inorder(root.right);
}

public static Node insert(Node root, int d)
{
   if(root == null)
   return root;

   if(root.data > d)
       root.left = insert(root.left,d);
   else if(root.data < d)
       root.right = insert(root.right,d);
   else
       root.count++;

   return root;
}

Example: Dry Run

arr[] = {1,2,2,2,2,3,5}

  • i = 0: Create a new node with data = 1, count = 1.
  • i = 1: Create a new node with data = 2, count = 1.
  • i = 2: Update count of node[data = 2, count = 1] to node[data = 2, count = 2].
  • i = 3: Update count of node[data = 2, count = 2] to node[data = 2, count = 3].
  • i = 4: Update count of node[data = 2, count = 3] to node[data = 2, count = 4].
  • i = 5: Create a new node with data = 3, count = 1.
  • i = 6: Create a new node with data = 4, count = 1.

Traverse the tree in inorder fashion and return the node with the maximum count value which is data = 2, count = 4 in the above example.

Time complexity

Inserting a node in the BST requires O(logN) time.

For N elemnts, this takes O(N * logN) time. Inorder traversal takes O(N) time. Hence, the time complexity is upper bound by O(N * logN).

Space complexity

For creating the BST, O(N) extra space is required. Hence, space complexity becomes O(N).

With this article at OpenGenus, you must have strong idea to find the Majority element in an array in multiple ways.

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.