Majority element

Posted: 5 Nov, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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
Approach 1

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.

Try Problem