Last Updated: 5 Nov, 2020

Majority element

Easy

Asked in companies

Solve now

Problem statement

You have been given an array/list 'ARR' consisting of 'N' integers. Your task is to find the majority element in the array. If there is no majority element present, print -1.

Note:

A majority element is an element that occurs more than floor('N' / 2) times in the array.

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains a single positive integer ‘N’ representing the size of the array/list.

The second line of each test case contains ‘N’ single space-separated integers representing the array elements of 'ARR'.

Output Format :

For each test case, print an integer denoting the majority element present in the array. Print-1 in case of no majority element.

Note :

You don't need to print the output, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 5 * 10^3
-10^5 <= ARR[i] <= 10^5

Where 'ARR[i]' denotes the element at the 'i'th index in the array/list 'ARR'.

Time limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea is to traverse the array and count the frequency of each element.

We will run two nested loops till ‘N’ and store the count of each array element in ‘maxCount’. If for any element, ‘maxCount' becomes greater than ‘N’ / 2, we will return that element as the majority element.

If no majority element is found, we will return -1.

Solve now

02 Approach

We will maintain a hashmap to store element-frequency pairs. We will traverse the array and store the frequency of each element in the hashmap.

If the frequency of any element becomes greater than the floor(N/2), we will return it as the majority element.

If no majority element is found, we will return -1.

Solve now

03 Approach

We can find the majority element in linear time and constant space using Moore’s voting algorithm. It is based on the fact that since the majority element occurs more than floor('N' / 2) times, its frequency will be greater than the combined frequencies of all other elements.

The algorithm gives the correct answer only if the majority element exists in the array. So, in the end, we have to check the frequency of the majority element to confirm.

The steps are as follows:

We will maintain ‘majorityElement’ to keep track of the possible candidate of the majority element.
We will initialize ‘count’ to 0 to store the count of ‘majorityElement'.
Loop through array elements.
1. If ‘count’ is 0:
  1. We set ‘majorityElement’ to the current element, set ‘count’ to 1, and continue iterating.
2. Else:
  1. If the current element is equal to the ‘majorityElement’, we increment the ‘count’ by 1.
  2. Else, we decrement the ‘count’ by 1.
Now, we again traverse through the array and find the count of ‘majorityElement’.
If the count is greater than floor('N' / 2), we return ‘majorityElement’ as the answer. Else, we return -1.

Solve now