Majority Element II Leetcode Solution

In this problem, we are given an array of integers. The goal is to find all the elements which occur more than ⌊N / 3⌋ time in the array where N = size of the array and ⌊ ⌋ is the floor operator. We need to return an array of such elements.

Range of elements: -10^9 to 10^9

Table of Contents

Example

Array = {1 , 2 , 3 , 3 , 2}

2 3

Explanation: ⌊N / 3⌋ = ⌊5 / 3⌋ = 1. Now, the integers 2 and 3 have frequencies equal to 2, which is greater 1. So, we print them.

Array = {1 , 2 , 3 , 4}

No majority elements

Explanation: We did not find any element whose frequency is greater than 1 in this case. So, we print “No Majority elements”.

Approach(Storing Frequencies)

As the title suggests, we can store the frequency of every element in the array using a hash table and then check for elements having a frequency greater than ⌊N / 3⌋. In this way, we can find all elements that satisfy the condition.

Algorithm

Initialize a HashMap-frequency to store the frequencies of elements in the array and a list/vector result to store the majority elements
For every element i in the array:
- Increment its frequency: frequency[i]++(or set as 1 if not present already)
For every key in the hashmap:
1. If frequency[key] > N / 3
  1. Add it to the result
Return the list result

Implementation of Majority Element II Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

vector<int> majorityElement(vector<int>& a)
{
    int N = a.size();
    vector <int> result;
    unordered_map <int , int> frequency;
    for(int &x : a)
        frequency[x]++;
    for(auto &x : frequency)
        if(x.second > N / 3)
            result.emplace_back(x.first);
    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 3 , 3 , 2};
    vector <int> result = majorityElement(a);
    if(result.empty())
        cout << "No majority elements\n";
    else
        for(int &x : result)
            cout << x << " ";
    return 0;
}

Java Program

import java.util.*;

class majority_element_ii
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 3 , 3 , 2};
        List <Integer> result = majorityElement(a);
        if(result.size() == 0)
            System.out.println("No majority elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> majorityElement(int[] a)
    {
        List <Integer> result = new ArrayList <Integer>();
        HashMap <Integer , Integer> frequency = new HashMap <>();

        for(int i = 0 ; i < a.length ; i++)
            frequency.put(a[i] , frequency.getOrDefault(a[i] , 0) + 1);

        for(Map.Entry i : frequency.entrySet())
        {
            Integer value = (int)i.getValue() , key = (int)i.getKey();
            if((int)value > ((a.length) / 3))
                result.add(key);
        }
        return result;
    }
}

2 3

Complexity Analysis of Majority Element II Leetcode Solution

Time Complexity

O(N) as we traverse the whole array once to update the frequencies. N = size of the array.

Space Complexity

O(N) as we use a hash table to store the frequencies.

Approach(Boyer-Moore Voting Algorithm)

The first thing to notice here is that there can be a maximum of 2 elements with a frequency greater than ⌊N / 3⌋ in the array. So, this problem becomes the same as the Majority Element problem with 2 majority elements this time.

We have already solved the Majority Element problem using Boyer-Moore’s Voting Algorithm. In the case of a single majority element, we could use the algorithm by comparing whether or not the current element is the candidate. But, in this case, we need to hold two potential majority elements and update their counters parallelly. With the help of this intuition, we can set our conditions as follows:

Set any two random candidates outside the range of elements in the array.
If the element is equal to either of the candidates, increment its counter.
If the counter of one candidate is equal to 0 at any point, we set the current element as the candidate if this current element is not the other candidate.
We decrease the counters of both candidates if the current element is not equal to either of the candidates.

In this way, we continue maintaining two different candidates parallelly in the array without the first candidate affecting the other. However, this is possible that the candidates we end up with are not the true majority elements( {1, 1, 2, 2, 3, 3} is one such example). Therefore, it is necessary to run a second pass to count the frequencies of candidates that we end up with. Based on this, we can return a vector of majority elements.