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

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:

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:

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:

Output:

`Element appearing more than n/2 times: 5`

__________________________________________________
Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

### 1 Response

1. lipsa patel says:

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.