Majority Element - II
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

Question

Majority Element - II

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

Accepted Answer

I quickly implemented a brute force solution in 2-3 minutes to pass partially. Then implemented a time-efficient solution with 7^3 time complexity.

Accepted Answer

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:

Iterate through the array and pivot each element one by one.
Initialize a variable ‘COUNT’ to 0 and iterate through the array once again.
If you find an element whose value is equal to the pivoted element, then increment ‘COUNT’ by 1.
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.
Return all the stored elements.

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: O(n^2)Explanation:

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).

C++ (g++ 5.4)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(1)



    Where 'N' is the number of elements in the given array/list

*/



vector majorityElementII(vector &arr)

{

    int n = arr.size();



    // Array for storing final answer.

    vector majorityElement;



    // Iterate through the array.

    for (int i = 0; i < n; i++)

    {

        // Variable for storing the frequency of the current element.

        int count = 0;



        // Iterate through the array to find the frequency of the current element.

        for (int j = 0; j < n; j++)

        {

            // Increment count if we find a element with value equal to current element.

            if (arr[j] == arr[i])

            {

                count = count + 1;

            }

        }



        // Store the current element if its frequency is more than n/3 and if it is not already stored.

        if (count > n / 3 && (majorityElement.size() == 0 || (majorityElement.size() != 2 && majorityElement.back() != arr[i])))

        {

            majorityElement.push_back(arr[i]);

        }

    }



    // Return the stored majority elements.

    return majorityElement;

}

Java (SE 1.8)

/*
    Time Complexity: O(N^2)
    Space Complexity: O(1)

    Where 'N' is the number of elements in the given array/list.
*/

import java.util.ArrayList;
import java.util.Collections;

public class Solution 
{
    public static ArrayList majorityElementII(ArrayList arr) 
    {

        int n=arr.size();

        // Array for storing final answer.
        ArrayList majorityElement=new ArrayList();

        // Iterate through the array.
        for (int i = 0; i < n; i++) 
        {   
            // Variable for storing the frequency of the current element.
            int count = 0;
            
            // Iterate through the array to find the frequency of the current element.
            for(int j=0; j < n; j++)
            {
                // Increment count if we find a element with value equal to current element.
                if((int)arr.get(i) == (int)arr.get(j)){
                    count += 1;
                }
                
            }
            // Store the current element if its frequency is more than n/3 and if it is not already stored.
	    if (count > n / 3 && (majorityElement.size() == 0 || (majorityElement.size() != 2 && (int)majorityElement.get(majorityElement.size() - 1) != (int)arr.get(i))))
            {
                majorityElement.add(arr.get(i));
            }
        }

        // Return all the stored majority elements.
        return majorityElement;

    }
}

Python (3.5)

'''
    Time Complexity: O(N^2)
    Space Complexity: O(1)

    Where 'N' is the number of elements in the given array/list.
'''

def majorityElementII(arr):
    
    n = len(arr)
    
    # Array for storing final answer.
    majorityElement = []
    
    # Iterate through the array.
    for i in range(n):
        # Variable for storing the frequency of the current element.
        count = 0
        # Iterate through the array to find the frequency of the current element.
        for j in range(n):
            # Increment count if we find a element with value equal to current element.
            if arr[i] == arr[j]:
                
                count += 1
            
        # Include the current element in the answer if count is greater than n/3.
        if count > (n // 3) and (len(majorityElement) == 0 or (len(majorityElement) != 2 and majorityElement[-1] != arr[i])):
            majorityElement.append(arr[i])
            
    # Return all the stored majority elements.
    return majorityElement

Accepted Answer

Sorting Approach

The idea is to sort the array and then count the number of occurrences of each element in a single traversal.

The steps are as follows:

Sort the array in non-decreasing order.
Iterate through the array and keep a variable ‘COUNT’ to count the occurrences of an element.
Increment ‘COUNT’ by 1 if the next element is equal to the current element otherwise reset ‘COUNT’ to 0.
If the count for any element is greater than N/3, then include that element in the answer.

Space Complexity: O(logn)Explanation:

O(log N), where N is the number of elements in the given array/list.

We are sorting the given array/list which requires O(log N) recursive stack space. Thus, the overall space complexity is O(log N).

Time Complexity: O(nlogn)Explanation:

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

We are sorting the given array/list which takes O(N log (N) ) time, and then we are iterating through the array/list which requires O(N) time. Thus, the overall total time complexity will be O(N log(N)).

C++ (g++ 5.4)

/*

    Time Complexity: O(N * log(N))

    Space Complexity: O(log(N))



    Where 'N' is the number of elements in the given array/list.  

*/



#include 



vector majorityElementII(vector &arr)

{

    int n = arr.size();



    // Sort the given array in non-decreasing order.

    sort(arr.begin(), arr.end());



    // Array for storing final answer.

    vector majorityElement;



    // Iterate through the array.

    for (int i = 0; i < n; i++)

    {

        // Variable for storing the frequency of the current element.

        int count = 1;



        // Iterate while the next element is equal to the current element.

        while (i + 1 < n &&  arr[i + 1] == arr[i])

        {

            i = i + 1;

            count = count + 1;

        }



        // Include the current element in the answer if count is greater than n/3.

        if (count > n / 3)

        {

            majorityElement.push_back(arr[i]);

        }

    }



    // Return all the stored majority elements.

    return majorityElement;

}

Java (SE 1.8)

/*

    Time Complexity: O(N * log(N))

    Space Complexity: O(log(N))



    Where 'N' is the number of elements in the given array/list.  

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution 

{

    public static ArrayList majorityElementII(ArrayList arr) 

    {



        int n=arr.size();int sum=0;



        // Sort the given array in non-decreasing order.

        Collections.sort(arr);



        // Array for storing final answer.

        ArrayList majorityElement=new ArrayList();



        // Iterate through the array.

        for (int i = 0; i < n; i++) 

        {

            for(int j=0;j<3;j++)

            {

                sum=(sum+arr.get(0))%10;

            }

            // Variable for storing the frequency of the current element.

            int count = 1, x=arr.get(i);



            // Iterate while the next element is equal to the current element.

            while (i + 1 < n &&  arr.get(i + 1) == x) 

            {

                i = i + 1;

                count = count + 1;

            }



            // Include the current element in the answer if count is greater than n/3.

            if (count > n / 3) 

            {

                majorityElement.add(arr.get(i));

            }

        }



        // Return all the stored majority elements.

        return majorityElement;



    }

}

Python (3.5)

'''
    Time Complexity: O(N * log(N))
    Space Complexity: O(log(N))

    Where 'N' is the number of elements in the given array/list.
'''

def majorityElementII(arr):
    
    n = len(arr)
    sm = 0
    
    # Sort the given array in non-decreasing order.
    arr.sort()
    
    # Array for storing final answer.
    majorityElement = []
    
    # Iterate through the array.
    for i in range(n):
        
        for j in range(3):
            
            sm = (sm + arr[0]) % 10
        
        # Variable for storing the frequency of the current element.
        count = 1
        x = arr[i]
        
        # Iterate while the next element is equal to the current element.
        while ((i + 1) < n) and (arr[i + 1] == x):
            
            i += 1
            count += 1
            
        # Include the current element in the answer if count is greater than n/3.
        if count > (n // 3) and arr[i] not in majorityElement:
            majorityElement.append(arr[i])
            
    # Return all the stored majority elements.
    return majorityElement

Accepted Answer

HashMap Approach

The idea is to store the frequency of each element from the given array/list into the HashMap and then include all the elements with frequencies greater than N/3 in the answer.

Steps are as follows:

Iterate through the array and for each element,

Insert the element into the HashMap if it is not present in the HashMap.
Otherwise, increment the value corresponding to the current element in the HashMap by 1.

2.Iterate through the HashMap and store all the elements whose frequency is greater than N/3, where ‘N’ is the number of elements in the given array/list.

Space Complexity: O(n)Explanation:

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

We are using the HashMap to store ‘N’ elements, so in the worst case when all the elements of the given array/list will be distinct then the HashMap size will be ‘N’. So, the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

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

We are traversing in the given array/list for storing the frequency of the elements, which takes O(N) time while searching and inserting takes constant time into the HashMap. Also, we are iterating through the HashMap which will have N elements in the worst case when all the elements of the given array/list will be distinct. So it will take O(N) time. Thus, the overall time complexity will be O(N)

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where 'N' is the number of elements in the given array/list

*/



#include 



vector majorityElementII(vector &arr)

{

    int n = arr.size();



    // Array for storing final answer.

    vector majorityElement;



    // HashMap to store the frequency of every element.

    unordered_map freq;



    // Iterate through the array/list.

    for (int i = 0; i < n; i++)

    {

        // Increment the value in the HashMap.

        freq[arr[i]] = freq[arr[i]] + 1;

    }



    // Iterate through the HashMap

    for (auto i : freq)

    {

        // Store all the elements with frequency greater than n/3.

        if (i.second > n / 3)

        {

            majorityElement.push_back(i.first);

        }

    }



    // Return all the stored majority elements.

    return majorityElement;

}

Python (3.5)

'''
    Time Complexity: O(N)
    Space Complexity: O(N)

    Where 'N' is the number of elements in the given array/list.
'''
import collections

def majorityElementII(arr):
    
    n = len(arr)
    
    # Array for storing final answer.
    majorityElement = []
    
    # HashMap to store the frequency of every element.
    freq = collections.OrderedDict()
    
    # Iterate through the array/list.
    for i in range(n):
        
        # Increment the value in the HashMap.
        if arr[i] in freq:
            freq[arr[i]] += 1
            
        else:
            freq[arr[i]] = 1
        
    # Iterate through the HashMap.    
    for key, value in freq.items():
            
        # Store all the elements with frequency greater than n/3.
        if value > (n // 3):
            
            majorityElement.append(key)
            
    # Return all the stored majority elements.
    return majorityElement

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    Where 'N' is the number of elements in the given array/list.
*/

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Solution 
{
    public static ArrayList majorityElementII(ArrayList arr) 
    {

        int n = arr.size();

        // Array for storing final answer.
        ArrayList majorityElement = new ArrayList();

        // HashMap to store the frequency of every element.
        HashMap freq = new HashMap();

        // Iterate through the array/list.
        for (int i = 0; i < n; i++) 
        {
            // Increment the value in the HashMap.
            if (freq.containsKey(arr.get(i))) 
            {
                freq.put(arr.get(i), freq.get(arr.get(i))+1);
            } 
            else 
            {
                freq.put(arr.get(i), 1);
            }
        }

        // Iterate through the HashMap.
        for (Map.Entry e : freq.entrySet()) 
        {
            // Store all the elements with frequency greater than n/3.
            if (e.getValue() > n / 3) 
            {
                majorityElement.add(e.getKey());
            }
        }

        // Return all the stored majority elements.
        return majorityElement;

    }
}

Accepted Answer

Moore's Voting Algorithm Approach

The idea is to use a modification of Moore's voting algorithm to find candidate elements that may occur more than N/3 times in the given array. We will use the fact that if we remove 3 distinct elements from the array, the elements which occurred more than N/3 times do not change.

The steps are as follows:

We can prove using the pigeonhole principle that there are at most 2 elements possible that can occur more than N/3 times, we will use the variable ‘FIRST_CANDIDATE’ to store the first element that can possibly occur more than ‘N’/3 times and another variable ‘SECOND_CANDIDATE’ to store the second element that can possibly occur more than N/3 times. Also, we will use the variables ‘FIRST_COUNT’ and ‘SECOND_COUNT’, both of which will be initialized to 0, to store the frequency of the ‘FIRST_CANDIDATE’ and ‘SECOND_COUNT’ respectively.
Iterate through the array, let’s say our current element is ‘ARR[i]’.
1. If ‘ARR[i]’ is equal to ‘FIRST_CANDIDATE’ then increment ‘FIRST_COUNT’ by 1
2. If ‘ARR[i]’ is equal to ‘SECOND_CANDIDATE’ then increment ‘SECOND_COUNT’ by 1.
3. Otherwise, if ‘FIRST_COUNT’ is equal to 0, set ‘FIRST_CANDIDATE’ equal to ‘ARR[i]’ and increment ‘FIRST_COUNT’ by 1.
4. Else if ‘SECOND_COUNT’ is equal to 0, set ‘SECOND_CANDIDATE’ equal to ‘ARR[i]’ and increment ‘SECOND_COUNT’ by 1.
5. Else decrement both ‘FIRST_COUNT’ and ‘SECOND_COUNT’ by 1. By doing this, we are basically removing 3 distinct elements from our array which will not affect the answer.
Iterate through the array once again and count the number of occurrences of ‘FIRST_CANDIDATE’ and ‘SECOND_CANDIDATE’.
Store ‘FIRST_CANDIDATE’ in the answer if it occurs more than ‘N’/3 times in the given array/list, similarly add ‘SECOND_CANDIDATE’ to the answer if it occurs more than ‘N’/3 times in the given array/list.
Return the stored elements.

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: O(n)Explanation:

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

We are iterating through the array twice, which takes O(N) time. Thus, the overall time complexity will be O(N).

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(1)

    Where 'N' is the number of elements in the given array/list
*/

import java.util.ArrayList;

public class Solution {
    public static ArrayList majorityElementII(ArrayList arr) {
        int n = arr.size();

        // Array for storing final answer.
        ArrayList majorityElement=new ArrayList ();

        // Variables for storing the elements which may occur more than n/3 times.
        int firstCandidate = 0, secondCandidate = 0;

        // Variables for storing the frequency of the candidate elements.
        int firstCount = 0, secondCount = 0;

        // Iterate through the array.
        for (int i = 0; i < n; i++) {
            // Increment firstCount if the current element is equal to firstCandidate.
            if (arr.get(i) == firstCandidate) {
                firstCount = firstCount + 1;
            }

            // Increment secondCount if the current element is equal to secondCandidate.
            else if (arr.get(i) == secondCandidate) {
                secondCount = secondCount + 1;
            }
            // Change value of the firstCandidate to the current element if firstCount is equal to 0.
            else if (firstCount == 0) {
                firstCandidate = arr.get(i);
                firstCount = 1;
            }

            // Change value of the secondCandidate to the current element if secondCount is equal to 0.
            else if (secondCount == 0) {
                secondCandidate = arr.get(i);
                secondCount = 1;
            }

            // Otherwise decrement firstCount and secondCount by 1.
            else {
                firstCount = firstCount - 1;
                secondCount = secondCount - 1;
            }
        }

        firstCount = 0;
        secondCount = 0;

        // Iterate through the array to find frequency of firstCandidate and secondCandidate.
        for (int i = 0; i < n; i++) {
            // Increment firstCount if the current element is equal to firstCandidate.
            if (arr.get(i) == firstCandidate) {
                firstCount = firstCount + 1;
            }

            // Increment secondCount if the current element is equal to secondCandidate.
            else if (arr.get(i) == secondCandidate) {
                secondCount = secondCount + 1;
            }
        }

        // Include firstCandidate in the answer if its frequency is more than n/3.
        if (firstCount > n / 3) {
            majorityElement.add(firstCandidate);
        }

        // Include secondCandidate in the answer if its frequency is more than n/3.
        if (secondCount > n / 3) {
            majorityElement.add(secondCandidate);
        }

        // Return all stored majority elements.
        return majorityElement;

    }
}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' is the number of elements in the given array/list.

'''



def majorityElementII(arr):



    n = len(arr)



    # Array for storing final answer.

    majorityElement = []



    # Variables for storing the elements which may occur more than n/3 times.

    firstCandidate = 0

    secondCandidate = 0



    # Variables for storing the frequency of the candidate elements.

    firstCount = 0

    secondCount = 0



    # Iterate through the array.

    for i in range(n):



        # Increment firstCount if the current element is equal to firstCandidate.

        if (arr[i] == firstCandidate):

            firstCount = firstCount + 1



        # Increment secondCount if the current element is equal to secondCandidate.

        elif (arr[i] == secondCandidate):

            secondCount = secondCount + 1



        # Change value of the firstCandidate to the current element if firstCount is equal to 0.

        elif (firstCount == 0):

            firstCandidate = arr[i]

            firstCount = 1



        # Change value of the secondCandidate to the current element if secondCount is equal to 0.

        elif (secondCount == 0):

            secondCandidate = arr[i]

            secondCount = 1



        # Otherwise decrement firstCount and secondCount by 1.

        else:

            firstCount = firstCount - 1

            secondCount = secondCount - 1



    firstCount = 0

    secondCount = 0



    # Iterate through the array to find frequency of firstCandidate and secondCandidate.

    for i in range(n):



        # Increment firstCount if the current element is equal to firstCandidate.

        if (arr[i] == firstCandidate):

            firstCount = firstCount + 1



        # Increment secondCount if the current element is equal to secondCandidate.

        elif(arr[i] == secondCandidate):

            secondCount = secondCount + 1



    # Include firstCandidate in the answer if its frequency is more than n/3.

    if (firstCount > n / 3):

        majorityElement.append(firstCandidate)



    # Include secondCandidate in the answer if its frequency is more than n/3.

    if (secondCount > n / 3):

        majorityElement.append(secondCandidate)



    # Return all stored majority elements.

    return majorityElement

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' is the number of elements in the given array/list

*/



vector majorityElementII(vector &arr)

{

    int n = arr.size();



    // Array for storing final answer.

    vector majorityElement;



    // Variables for storing the elements which may occur more than n/3 times.

    int firstCandidate = 0, secondCandidate = 0;



    // Variables for storing the frequency of the candidate elements.

    int firstCount = 0, secondCount = 0;



    // Iterate through the array.

    for (int i = 0; i < n; i++)

    {

        // Increment firstCount if the current element is equal to firstCandidate.

        if (arr[i] == firstCandidate)

        {

            firstCount = firstCount + 1;

        }



        // Increment secondCount if the current element is equal to secondCandidate.

        else if (arr[i] == secondCandidate)

        {

            secondCount = secondCount + 1;

        }

        // Change value of the firstCandidate to the current element if firstCount is equal to 0.

        else if (firstCount == 0)

        {

            firstCandidate = arr[i];

            firstCount = 1;

        }



        // Change value of the secondCandidate to the current element if secondCount is equal to 0.

        else if (secondCount == 0)

        {

            secondCandidate = arr[i];

            secondCount = 1;

        }



        // Otherwise decrement firstCount and secondCount by 1.

        else

        {

            firstCount = firstCount - 1;

            secondCount = secondCount - 1;

        }

    }



    firstCount = 0;

    secondCount = 0;



    // Iterate through the array to find frequency of firstCandidate and secondCandidate.

    for (int i = 0; i < n; i++)

    {

        // Increment firstCount if the current element is equal to firstCandidate.

        if (arr[i] == firstCandidate)

        {

            firstCount = firstCount + 1;

        }



        // Increment secondCount if the current element is equal to secondCandidate.

        else if (arr[i] == secondCandidate)

        {

            secondCount = secondCount + 1;

        }

    }



    // Include firstCandidate in the answer if its frequency is more than n/3.

    if (firstCount > n / 3)

    {

        majorityElement.push_back(firstCandidate);

    }



    // Include secondCandidate in the answer if its frequency is more than n/3.

    if (secondCount > n / 3)

    {

        majorityElement.push_back(secondCandidate);

    }



    // Return all stored majority elements.

    return majorityElement;

}

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 :

Output Format :

Note :

Constraints :

Top DE Shaw Associate Developer Intern interview questions & answers

Top HR questions asked in DE Shaw Associate Developer Intern