Majority Element II Leetcode Solution


Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Facebook Google Microsoft Zenefits
Array

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

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

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

Algorithm

  1. Initialize candOne and candtwo to store the two candidates and their frequencies cntOne and cntTwo as 0.
  2. For every element in the array:
    • If candOne == i:
      • cntOne++
    • else if candTwo == i
      • cntTwo++
    • else if cntOne == 0
      • Assign i as candOne: candOne = i
      • Set its count as 1: cntOne = 1
    • else if cntTwo == 0
      • candTwo = i
      • cntTwo = 1
    • Decrement counts of both candidates:
      • cntOne–
      • cntTwo–
  3. Set their counts back to zero for the second pass: cntOne = 0 and cntTwo = 0
  4. For every element in the array:
    • if it is equal to candOne:
      • cntOne++
    • else if it is equal to candTwo:
      • cntTwo++
  5. Initialize a list/vector result to store majority elements
  6. If cntOne > N / 3
    • Push candOne to result
  7. If cntTwo > N / 3
    • Push candTwo to result
  8. Print the result

Illustration:

Majority Element II Leetcode Solution

Implementation of Majority Element II Leetcode Solution

C++ Program

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

vector <int> majorityElement(vector <int> &a)
{
    vector <int> result;
    int candOne = (int)1e9 + 1 , candTwo = (int)1e9 + 1 , cntOne = 0 , cntTwo = 0;
    for(int &i : a)
    {
        if(candOne == i)
            cntOne++;
        else if(candTwo == i)
            cntTwo++;
        else if(cntOne == 0)
        {
            candOne = i;
            cntOne++;
        }
        else if(cntTwo == 0)
        {
            candTwo = i;
            cntTwo++;
        }
        else
        {
            cntOne--;
            cntTwo--;
        }
    }

    cntOne = 0;
    cntTwo = 0;
    for(int &i : a)
    {
        if(i == candOne)
            cntOne++;
        if(i == candTwo)
            cntTwo++;
    }

    if(cntOne > ((int)a.size()) / 3)
        result.push_back(candOne);
    if(cntTwo > ((int)a.size()) / 3)
        result.push_back(candTwo);

    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<>();

        int candOne = (int)1e9 + 1 , candTwo = (int)1e9 + 1 , cntOne = 0 , cntTwo = 0;
        for(int i : a)
        {
            if(candOne == i)
                cntOne++;
            else if(candTwo == i)
                cntTwo++;
            else if(cntOne == 0)
            {
                candOne = i;
                cntOne++;
            }
            else if(cntTwo == 0)
            {
                candTwo = i;
                cntTwo++;
            }
            else
            {
                cntOne--;
                cntTwo--;
            }
        }

        cntOne = 0;
        cntTwo = 0;
        for(int i : a)
        {
            if(i == candOne)
                cntOne++;
            if(i == candTwo)
                cntTwo++;
        }

        if(cntOne > (a.length) / 3)
            result.add(candOne);
        if(cntTwo > (a.length) / 3)
            result.add(candTwo);

        return result;
    }
}
3 2

Complexity Analysis of Majority Element II Leetcode Solution

Time Complexity

O(N) as we run two passes of the array irrespective of the input. N = size of the array.

Space Complexity

O(1) as we constant memory space.