Majority element in the array

Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

Problem: Given an array consisting of N integers, find the number with the maximum occurrences, i.e. majority element, given the assumption that the number occurs more than N/2 times in the array.

Example
I/P : 3 3 4 2 4 4 2 4 4
O/P : 4

I/P : 3 3 4 2 4 4 2 4
O/P : NONE

METHOD 1 (Basic)
The basic solution is to have two loops and keep track of maximum count for all different elements. If maximum count becomes greater than n/2 then break the loops and return the element having maximum count. If maximum count doesn’t become more than n/2 then majority element doesn’t exist.
Time Complexity: O(n*n).
Auxiliary Space : O(1).

METHOD 2 (Using Binary Search Tree)

We can have a binary search tree with an extra field count, which indicates the number of times an element appeared in the input. 
Node of the Binary Search Tree (used in this approach) will be as follows.

struct tree
{
  int element;
  int count;
}BST;

Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return.
The method works well for the cases where n/2+1 occurrences of the majority element is present in the starting of the array, for example {1, 1, 1, 1, 1, 2, 3, 4}.

Time Complexity: If a binary search tree is used then time complexity will be O(n^2). If a self-balancing-binary-search tree is used then O(nlogn)
Auxiliary Space: O(n)


METHOD 3 (Using Moore’s Voting Algorithm)
Given the assumption that the element occurs more than N/2 times in the array simplifies the solution a lot. This is so because if more than N/2 elements are the same, it implies that all other elements combined are less than N/2. Hence, the difference between the count of majority element and the count of non-majority numbers will always be positive. This approach can significantly simplify our code to the problem.


This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.

1. Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.


In the solution we consider the first element as the majority element and keep the count as 1. Now we compare the second (next) element with this element. If it is the same element we increase the count to 2, else decrease the count to ZERO and keep the first element as the majority element. Check the next element. If it is equal increase the count, else set the majority element to be the given current element and make the count as ONE.


This way, at the end of the traversal of the list, we will have the majority element with us.

Time complexity - As comparison between two elements takes constant time, the code will run in O(n) time where n is the number of elements in the list.

public static void printMajorElement(String[] args) {
  int[] list = new int[] {1, 2, 3, 4, 2, 3, 4, 2, 3, 2, 1, 2, 3, 4, 2, 2, 2};
   
  int count = 1;
  int majorityElement = list[0];
  for(int index = 1; index < list.length; index++) {
   if(majorityElement != list[index]) {
    if(count == 0) {
     majorityElement = list[index];
     count++;
    } else {
     count--;
    }
   } else {
    count++;
   }
  }
   
  System.out.println("Majority Element: " + majorityElement);
 }

Dry running the above program:
Lets consider the array A = {1,2,3,4,2,3,2,1,2,3,4,2,2,2}

Initially, majority element = 1 i.e. list(0), count=1
Now we traverse through the array. As next eleement is 2, we decrement the count to 0 because majorityElement 1 is not equal to list[1];

Now, we have count = 0. Again 1 is not equal to 3 and this time count=0, hence we change majority element to 3, count =1.

Now we have 4, and as 3!=4, we decrement count again.

 Next time 3!=2, we again decrement count, and point majority element to 2, and increment count =2.

Hence we see depending on if count>0, we are getting a majority element.

Thanks.