Majority Element – Part 1

Objective:  Given an array of integer write an algorithm to find the majority element in it (if exist).

Majority Element: If an element appears more than n/2 times in array where n is the size of the array.

Example:

int [] arrA = {1,3,5,5,5,5,4,1,5};
Output: Element appearing more than n/2 times: 5

int []arrA = {1,2,3,4};
Output: No element appearing more than n/2 times

Click here to read O(n) approach-Boyer–Moore majority vote algorithm

Approach 1: Brute Force

Use nested for loops and count each element and if count>n/2 for each element.

Time Complexity: O(n^2)

Code:

public class MajorityElementBruteForce {
public static void find(int [] arrA){
boolean found = false;
for (int i = 0; i <arrA.length ; i++) {
int x = arrA[i];
int count = 1;
for (int j = i+1; j <arrA.length ; j++) {
if(x==arrA[j])
count++;
}
if(count>arrA.length/2) {
System.out.println("Element appearing more than n/2 times: " + x);
found = true;
}
}
if(!found)
System.out.println("No element appearing more than n/2 times");
}
public static void main(String[] args) {
int [] arrA = {1,3,5,5,5,5,4,1,5};
find(arrA);
}
}

Approach 2: Hash Map

  • Store the count of each element in Hash map.
  • Iterate through hash map and check if any element has count >n/2

Time Complexity: O(n), Space Complexity: O(n)

Code:

import java.util.*;
public class MajorityElementHashing {
public static void find(int [] arrA){
boolean found = false;
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i <arrA.length ; i++) {
if(map.containsKey(arrA[i])){
int count = map.get(arrA[i]);
map.put(arrA[i],++count);
}else
map.put(arrA[i],1);
}
Set set = map.keySet();
Iterator<Integer> iterator = set.iterator();
while (iterator.hasNext()){
int key = iterator.next();
if(map.get(key)>arrA.length/2){
System.out.println("(Hashing)Element appearing more than n/2 times: " + key);
found = true;
break;
}
}
if(!found)
System.out.println("No element appearing more than n/2 times");
}
public static void main(String[] args) {
int [] arrA = {1,3,5,5,5,5,4,1,5};
find(arrA);
}
}

Approach 3: Sorting

  • Sort array, this will bring all the same elements together.
  • Iterate through array and check if any element has count >n/2

Time Complexity: O(nlogn), Space Complexity: O(1)

Code:

import java.util.*;
public class MajorityElementSorting {
public static void find(int [] arrA){
if(arrA.length==0)
return;
boolean found = false;
Arrays.sort(arrA);
int count = 1;
int x = arrA[0];
for (int i = 1; i <arrA.length ; i++) {
if(x==arrA[i]){
count++;
if(count>arrA.length/2) {
System.out.println("(Sorting)Element appearing more than n/2 times: " + x);
found = true;
break;
}
}else{
x = arrA[i];
count = 1;
}
}
if(!found)
System.out.println("No element appearing more than n/2 times");
}
public static void main(String[] args) {
int [] arrA = {1,3,5,5,5,5,4,1,5};
find(arrA);
}
}

Output:

Element appearing more than n/2 times: 5

1 thought on “Majority Element – Part 1”

Leave a Reply to lipsa patel Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.