Finding the majority element in an array

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: [1,2,3,1,1,1,1]

Output: 1

Example 2:

Input: [6,4,6,4,4,4]

Output: 4

Solution

This problem, if solved by brute force by checking for each and every element’s frequency, will be more complex and therefore can’t give an efficient solution.

Before going to the required solution, we must see the condition for an element to become a majority element once again:

The majority element is the element that appears more than [n/2] times.

The logic behind an efficient solution is based on this condition. We know that the majority element will occur more than n/2 times. This means that the values of the majority element will occur for more than half of the length of the given array.

So if we sort the whole array in increasing order, then n/2th element in the sorted will be equal to the majority element, as it occurs more than n/2 times.

Solution Implementation

• C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> vec = { 2, 2, 2, 3, 2 };
    
    sort(vec.begin(), vec.end());
    
    cout << "Majority Element is " << vec[vec.size()/2] << "\n";
    
    return (0);
}

Complexity Analysis:

• Time Complexity: O(nlogn)
• Space Complexity: O(1) or O(n), We sorted nums in place here – if that is not allowed, then we must spend linear additional space on a copy of nums and sort the copy instead.