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

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.

 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:

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.

 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/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;