Majority element
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

Question

Majority element

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

Accepted Answer

Brute Force 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.

Space Complexity: O(1)Explanation:

O(1)

Since constant space is used, space complexity will be O(1).

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ denotes the size of the given array/list.

Since we are running two nested loops till ‘N’ to count the frequency of each element. Thus the overall time complexity is O(N^2).

Accepted Answer

Using HashMap

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.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ denotes the size of the given array/list.

Since we are storing the elements of the array and their respective frequencies in a hashmap. In the worst case, when the array contains ‘N’ distinct elements, then the hashmap takes O(N) space. Thus the space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ denotes the size of the given array/list.

Since we are traversing the array exactly one time in O(N) time. Thus the time complexity will be O(N).

Accepted Answer

Boyer-Moore majority vote algorithm

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.