Majority Element

Easy
0/40
11 upvotes
Asked in companies
AmazonSamsung R&D InstituteQualcomm

Problem statement

Given an array/list of length ‘N’, you are supposed to return the majority element of the array/list.

The majority element is the element that appears more than floor(N/2) times in the given array/list.

Note: 
You may assume that the given array/list is non-empty and the majority element always exists in the array.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array/list.

The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.
Output format: 
For each test case, print the majority element in a separate line.
Note: 
You do not need to print anything; it has already been taken care of.
Constraints: 
1 <= T <= 50
1 <= N <= 10^4
0 <= ARR[i] <= 10^5

Where ‘T’ is the number of test cases.
'N' is the length of the given array/list.
And, ARR[i] denotes the i-th element in the array/list.

Time Limit: 1 sec.
Sample Input 1:
2
3
1 2 2
5
4 2 1 4 4
Sample Output 1:
2
4
Explanation to Sample Input 1:
In the first test case, the floor(N/2) is 1, and there is only one element, i.e. 2 whose occurrence is 2, which is greater than 1. No other elements have occurrence greater than 1.

In the second test case, the floor(N/2) is 2, and there is only one element i.e. 4 whose occurrence is 3, which is greater than 2. No other elements have occurrence greater than 2.
Sample Input 2:
2
5
2 2 2 3 3
9
5 1 5 1 5 5 5 5 5
Sample Output 2:
2
5
Explanation to Sample Input 2:
In the first test case, the floor(N/2) is 2, and there is only one element, i.e. 2 whose occurrence is 3, which is greater than 2. No other elements have occurrence greater than 2.

In the second test case, the floor(N/2) is 4, and there is only one element i.e. 5 whose occurrence is 7, which is greater than 4. No other elements have occurrence greater than 4.
Hint

Check for each element, whether it occurs more than floor(N/2) times in the given array/list.

Approaches (4)
Brute Force

The idea is to count the number of times each element occurs and if any element occurs more than N/2 times, then include it in our answer.

 

Steps are as follows :

 

  1. Create a variable to store the maximum count, let’s say “count”.
  2. Traverse through the given array/list from start to the end.
  3. While Iterating through the array, pivot each element one by one.
  4. Initialise a variable “count” to 0 and iterate through the array once again.
  5. If you find an element whose value is equal to the pivoted element, then increment “count” by 1.
  6. After iterating through the array if the value of “count” is more than N/2, then return that element as the answer.
Time Complexity

O(N^2), where ‘N’ is the number of elements in the given array/list.

 

We are pivoting every element once and for every element, we are traversing the given array/list. So there will be a total of ‘N’ elements to pivot and then to traverse the given array/list will take O(N) time. Thus, the total time complexity will be O(N^2).

Space Complexity

O(1)

 

Since no extra space is required, so the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Majority Element
Full screen
Console