### Majority Element - The Coding Shala

Home >> Interview Prep >> Majority Element

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

## Majority Element Problem

Given the array nums of size n, return the majority element.

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:
Input: nums = [3,2,3]
Output: 3

Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 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;
}
}
```

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

Time Complexity: O(n)

Space Complexity: O(1)

Java Program:

```class Solution {
public int majorityElement(int[] nums) {
int count = 1;
int majority = nums;
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