### Majority Element - The Coding Shala

In this post, we will learn how to find Majority Element in the array and will implement its solution in Java.

## Majority Element Problem

The majority element is the element that appears more than n / 2 times. You may assume that the majority element always exists in the array.

**Example 1:**

**Example 2:**

## Majority Element Java Solution

**Approach 1**

First sort the array then find the frequency of elements, if the count is greater than n/2 return that.

Time Complexity: O(nlogn) [sorting]

We can use HashMap to store the counts of elements that will take additional O(n) space.

**Java Program: **

class Solution { public int majorityElement(int[] nums) { int check = nums.length/2; Arrays.sort(nums); int count = 1; for(int i=1; i<nums.length; i++) { if(nums[i] == nums[i-1]) count++; else count = 1; if(count > check) { return nums[i]; } } return nums[0]; } }

**Approach 2**

Modification in Sorting approach.

We know that the Majority element comes more than n/2 time. After sorting the array the middle element is always the Majority element.

**Java Program: **

class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; } }

**Approach 3**

Boyer-Moore Voting Algorithm. [Read Here]

Time Complexity: O(n)

Space Complexity: O(1)

**Java Program: **

class Solution { public int majorityElement(int[] nums) { int count = 1; int majority = nums[0]; for(int i=1; i<nums.length; i++) { if(count == 0) { majority = nums[i]; count = 1; } else if(majority == nums[i]) count++; else count--; } return majority; } }

**Other Posts You May Like**

- Move Zeroes
- Count Number of Inversions
- Sort an Array according to set bits
- How to find the second largest element in the array
- Find first duplicate in the array

## Comments

## Post a Comment