Majority Element Leetcode Solution - TutorialCup majority

Table of Contents

Problem Statement

We are given an array of integers. We need to return the integer which occurs more than ⌊N / 2⌋ time in the array where ⌊ ⌋ is the floor operator. This element is called the majority element. Note that the input array always contains a majority element.

Example

Array = {1 , 3 , 3 , 3}

Exaplanation: ⌊N / 2⌋ = 4 / 2 = 2. And the integer ‘3’ occurs 3 times in the array.

Array = {1 , 1 , 2}

Explanation: ⌊N / 2⌋ = ⌊3 / 2⌋ = 1. And ‘1’ occurs 2 times in the array.

Approach(Hashtable)

We can store the frequency of every element in the array in a hash table. It then becomes easy to check for an integer having frequency > ⌊N / 2⌋.

Algorithm

Initialize a hash table to store the frequency of integers in the array: frequency
For every element, i, in the array:
- Increment frequency[i] or set frequency[i] = 0 if it is not in the table already
- If frequency[i] > N / 2:
  - return i
Return -1 (to avoid compilation error)
Print the result

Implementation of Majority Element Leetcode Solution

C++ Program

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

int majorityElement(vector <int> &a)
{
    int majorityCount = ((int) a.size()) / 2;
    unordered_map <int , int> frequency;
    for(int &i : a)
    {
        if(++frequency[i] > majorityCount)
            return i;
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
    cout << majorityElement(a) << '\n';
    return 0;
}

Java Program

import java.util.*;

class majority_element
{
    public static void main(String args[])
    {
        int[] a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
        System.out.println(majorityElement(a));
    }

    static int majorityElement(int[] a)
    {
        HashMap <Integer , Integer> frequency = new HashMap<>();
        for(int i = 0 ; i < a.length ; i++)
        {
            frequency.put(a[i] , frequency.getOrDefault(a[i] , 0) + 1);
            if(frequency.get(a[i]) > a.length / 2)
                return a[i];
        }
        return -1;
    }
}

Complexity Analysis of Majority Element Leetcode Solution

Time Complexity

O(N) as we traverse the array once to find the majority element. N = size of the array.

Space Complexity

O(N) as the maximum number of distinct elements in the array can be: N – ⌊N / 2⌋ as the majority element occupies at least ⌊N / 2⌋ indices. Therefore, the space complexity is linear.

Approach(Boyer-Moore Voting Algorithm)

This problem is a nice illustration of how can we find a majority element in a stream of elements. The Boyer-Moore Voting algorithm is used to find the element that occupies more than ⌊N / 2⌋ places in a sequence. This algorithm maintains a candidate and its count in the array. We run a single pass of the array with candidate = -1 and count = 0. If any element in the array is the candidate, we increment count. Otherwise, we decrement it. If the count becomes zero, we change the candidate and set its count back to 0.

In order to understand its functioning, follow the example below:

This algorithm considers the process as an election and first decides a candidate. The one who gets the most votes is the majority candidate. In the above example, we choose a candidate as 1 initially, but as we reach index 4 in the array, we observe that count = 0, which means that we have seen as many candidates as non-candidates. So, we choose the current element as a candidate and continue the process. Since we are guaranteed to have a majority element in the array, the last candidate we are left with will be the majority element.

Algorithm

Initialize two variables: candidate and cnt to store the candidate and its frequency for respective iterations
Now, for every element i in the array:
- If cnt is equal to zero:
  - update: candidate = i
- If i is equal to candidate:
  - increment cnt: cnt++
- Else:
  - Decrement cnt: cnt–
Return candidate
Print the result

Implementation of Majority Element Leetcode Solution

C++ Program

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

int majorityElement(vector <int> &a)
{
    int candidate = -1 , cnt = 0;
    for(int &i : a)
    {
        if(cnt == 0)
            candidate = i;
        cnt += (candidate == i) ? 1 : -1;
    }
    return candidate;
}

int main()
{
    vector <int> a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
    cout << majorityElement(a) << '\n';
    return 0;
}

Java Program

import java.util.*;

class majority_element
{
    public static void main(String args[])
    {
        int[] a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
        System.out.println(majorityElement(a));
    }

    static int majorityElement(int[] a)
    {
        int candidate = -1 , cnt = 0;
        for(int i = 0 ; i < a.length ; i++)
        {
            if(cnt == 0)
                candidate = a[i];
            cnt += (candidate == a[i]) ? 1 : -1;
        }
        return candidate;
    }
}