Skip to main content
  1. Problem Solving Solutions/

Majority Element LeetCode Solution

·2 mins
leetcode
Mayukh Datta
Author
Mayukh Datta
Table of Contents

Given an array of size n, find the majority element. The majority element is the element that appears more than [ n/2 ] times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3] Output: 3

Example 2:

Input: [2,2,1,1,1,2,2] Output: 2

Link: https://leetcode.com/problems/majority-element/

Solution using unordered_map in C++: #

class Solution { public: int majorityElement(vector& a) { unordered_map<int, int> mp; int n = a.size();

    for(int i=0;i<n;i++) {
        mp\[a\[i\]\]++;
    }
    
    for(int i=0;i<n;i++) {
        if(mp\[a\[i\]\] > (n/2)) {
            n = a\[i\];
            break;
        }
    }
    
    return n;
}

};

It has \(O(n)\) time complexity and \(O(n)\) space complexity.

Solution using the Boyer-Moore voting algorithm in C++ #

class Solution { public: int majorityElement(vector& a) { int count, candidate, n;

    n = a.size();
    
    // finding the candidate
    candidate = a\[0\];
    count = 1;
    for(int i=1;i<n;i++) {
        if(candidate != a\[i\]) {
            count--;
        }else{
            count++;
        }
        
        if(count == 0) {
            candidate = a\[i\];
            count = 1;
        }
    }
    
    // find the majority candidate
    count = 0;
    for(int i=0;i<n;i++) {
        if(a\[i\] == candidate) {
            count++;
        }
        
        if(count > (n/2)) {
            break;
        }
    }
    
    return candidate;
}

};

Time complexity is same as the previous solution but we improved the space complexity to \(O(1)\).

The algorithm is well explained here

https://youtu.be/n5QY3x_GNDg