Majority Element - II

Easy
0/40
Average time to solve is 10m
181 upvotes
Asked in companies
Morgan StanleyAmazonD.E.Shaw

Problem statement

You are given an array/list 'ARR' of integers of length ‘N’. You are supposed to find all the elements that occur strictly more than floor(N/3) times in the given array/list.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases follow.

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

The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.
Output Format : 
For each test case, return all the majority elements separated by a single space.

The output of every test case will be printed in a separate line.

You may return the majority of elements in any order.
Note : 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 100
3 <= N <= 5000
1 <= ARR[i] <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
7
3 2 2 1 5 2 3
5
7 4 4 9 7
Sample Output 1:
2
4 7
Explanation of Sample Input 1:
In the first test case, floor(N/3) = floor(7/3) is equal to 2, and 2 occurs 3 times which is strictly more than N/3. No other element occurs more than 2 times.

In the second test case, floor(N/3) = floor(5/3) is equal to 1, and 4 and 7 both occur 2 times. No other element occurs more than once.
Sample Input 2:
2
6
1 2 4 4 3 4
4
6 6 6 7
Sample Output 2:
4
6
Explanation of Sample Input 2:
In the first test case, floor(N/3) = floor(6/3) is equal to 2, and 4 occurs 3 times which is strictly more than N/3. No other element occurs more than 2 times.

In the second test case, floor(N/3) = floor(4/3) is equal to 1, and 6 occurs 3 times. No other element occurs more than once.
Hint

Check for each element, whether it occurs more than N/3 times or not.

Approaches (4)
Brute Force

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

 

The steps are as follows:

  1. Iterate through the array and pivot each element one by one.
  2. Initialize a variable ‘COUNT’ to 0 and iterate through the array once again.
  3. If you find an element whose value is equal to the pivoted element, then increment ‘COUNT’ by 1.
  4. After iterating through the array if the value of ‘COUNT’ is more than n/3, then store the pivot element if it hasn’t already been included in the answer.
  5. Return all the stored elements.
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).

 

We are not using any extra space. Thus, the space complexity will be O(1).

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