**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

In Nested Loop approach, break the loop after found=true;