Majority Element LeetCode Solution

·2 mins
Leetcode

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

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