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:

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.

 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:

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;