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

https://gist.github.com/thmain/e5fae88a86ef8ba5000a02af309e1be7

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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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;