# 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
```

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/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 map = new HashMap(); for (int i = 0; i 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; for (int i = 1; i 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”

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