Majority element in the array


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).

 Write a function which takes an array and prints the majority element (if it exists), otherwise prints “No Majority Element”.
Naive solution using HashMap : Space complexity = O(n) Time complexity = O(n)

HashMap stores key value pairs. The keys must be unique. We iterate through all the elements in the array. If the element is already present in the hashmap then we get its count, increment it by 1. If the count is greater than n/2 then we print the majority element. Else We put the updated count into the hashmap. 
    If the element is not already present in the hashmap then we put the element into the hashmap with its count set to zero.

Code:
import java.util.*;

public class Solution {

    static void findMajorityElement(int[] a) {
        int n = a.length;
        HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
        
        for(int i=0; i<n; i++){
            if(hashmap.containsKey(a[i])){
                int count = hashmap.get(a[i])+1;
                if(count> n/2){
                    System.out.print("Majority Element is: "+a[i]);
                    return;
                }
                else{
                    hashmap.put(a[i],count);
                }
            }
            else{
                hashmap.put(a[i],1);
            }
            
        }
        
        System.out.print("No Majority Element");
        
      return;
}

    public static void main(String[] args) {
        int[] a = {2,2,2,2,5,5,2,3,3};
        findMajorityElement(a);
        
        
}
}


Efficient Solution using Moore's voting algorithm: space complexity O(1) and O(n) time complexity

Here we will assume first element as the majority element and count its occurrence. We will increment the counter if the element is same and decrement  if it is different. If the counter reaches zero we will reset the element to the present element and counter to 1. If the majority element is present in the array then it will be stored in element. We will check this by running another loop.

Code:
import java.util.*;

public class Solution {

    static void findMajorityElement(int[] a) {
        int n = a.length;
        int count = 1;
        int element = a[0];
        for(int i=1; i<n; i++){
            if(a[i] ==  element){
                count++;
            }
            else{
                count--;
            }
            if(count == 0){
                element = a[i];
                count = 1;
            }
        }
        count = 0;
        for(int i=0; i<n; i++){
            if(element == a[i])
                count++;
        }
        if(count > n/2){
            System.out.print("Majority element is "+ element);
        }
        else
            System.out.print("No majority element");
        
        
      return;
}

    public static void main(String[] args) {
        int[] a = {3, 3, 4, 2, 4, 4, 2, 4, 4};
        findMajorityElement(a);
        
        
}
}

Output:

Majority element is 4


Explanation:




  This problem can also be solved in O(nlogn) time complexity and O(1) splace complexity by sorting the array using nlogn sorting algorithm and then counting the occurrences. 















Comments

Post a Comment

Popular posts from this blog

Rearrange Array in Maximum-Minimum form

Given a sorted array of positive integers, rearrange the array alternately i.e first element should be the maximum value, second minimum value, third-second max, fourth-second min and so on. Naive Solution: Here we will use an auxiliary array to store the elements in correct order. For even indices of the array  Large numbers from the given array are added. For odd indices small numbers are added. Code: import java.util.*; public class Test{        public static void main(String[] args) {          Scanner in = new Scanner(System.in);     int[] a = {1,2,3,4,5,6,7,8,9};     int n = a.length;     int[] temp = new int[n];     int small = 0;     int large = n-1;     for(int i=0; i<n; i++){         if(i%2 == 0){             temp[i] = a[large--];         }  ...
Read more

Write a progtam to calculate size of a tree

Recursion Steps:   Size of a tree= 1+size of left subtree + size of right subtree   Base case : return zero if  a node is null Code:     Time:O(n) class Node{     int data;     Node left, right;     Node(int data){         this.data = data;     } } public class SizeOfBinaryTree {       static int calculateSize(Node node){           if(node == null){               return 0;           }                     return (1+calculateSize(node.left)+calculateSize(node.right));       }             public static void main(String[] args){      ...
Read more