Majority Element - II

Posted: 20 Nov, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.

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

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.
Try Problem