Majority element

Problem Statement

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

       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

Link to GitHub: Code

O(n) time O(1) space fastest solution

note: Since we are assuming that majority element always exist we do not have to check for more than n/2 times more.

Solution

• Take the first element as the majority element
• Check if the next element is equal to majority element. If  yes then increment or decrement the counter
• Note: If the counter is 0 then we need to reset it to 1

package Algorithms.Arrays;
/*
 *        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
 */

public class MajorityElement {
 
 public static int get(int [] arr)
 {
  //We are taking the first element of the array
  int major=arr[0], count=1;
   
  for(int i=1;i<arr.length;i++)
  { 
   //If count is set to zero during iteration we need 

   // to reset the count
   if (count==0)
   {
    count++;
    major=arr[i];
   }
   //If current element is same as major then increment the count
   else if(major==arr[i])
   {
    count++;
   }
   //If we are here than we know that the current element 

   //is not the same then we would decrement the count
   else
   {
    count--;
   }
   
  }
  return major;
  
 }

}

Iteration