# 169. Majority Element

## Modern C++ with std::nth_element

·

### Problem statement

Given an array `nums` of size `n`, return the majority element.

The majority element is the element that appears more than `⌊n / 2⌋` times. You may assume that the majority element always exists in the array.

#### Example 1

``````Input: nums = [3,2,3]
Output: 3
``````

#### Example 2

``````Input: nums = [2,2,1,1,1,2,2]
Output: 2
``````

#### Constraints

• `n == nums.length`.

• `1 <= n <= 5 * 10^4`.

• `-2^31 <= nums[i] <= 2^31 - 1`.

#### Follow-up:

Could you solve the problem in linear time and in `O(1)` space?

### Solution 1: Counting the frequency

#### Code

``````#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;
int majorityElement(vector<int>& nums) {
unordered_map<int,int> freq;
const int HALF = nums.size() / 2;
for (int a : nums) {
freq[a]++;
if (freq[a] > HALF) {
return a;
}
}
return nums[0];
}
int main() {
vector<int> nums{3,2,3};
cout << majorityElement(nums) << endl;
nums = {2,2,1,1,1,2,2};
cout << majorityElement(nums) << endl;
}
``````
``````Output:
3
2
``````

#### Complexity

• Runtime: `O(n)`, where `n = nums.length`.

• Extra space: `O(n)`.

### Solution 2: Sorting and picking the middle element

#### Code

``````#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size()/2];
}
int main() {
vector<int> nums{3,2,3};
cout << majorityElement(nums) << endl;
nums = {2,2,1,1,1,2,2};
cout << majorityElement(nums) << endl;
}
``````
``````Output:
3
2
``````

#### Complexity

• Runtime: `O(nlogn)`, where `n = nums.length`.

• Extra space: `O(1)`.

### Solution 3: Partial sort

Since you are interested in only the middle element after sorting, the partial sorting algorithm `std::nth_element` can be used in this case to reduce the cost of the full sorting.

#### Code

``````#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int majorityElement(vector<int>& nums) {
const int mid = nums.size() / 2;
std::nth_element(nums.begin(), nums.begin() + mid, nums.end());
return nums[mid];
}
int main() {
vector<int> nums{3,2,3};
cout << majorityElement(nums) << endl; // 3
nums = {2,2,1,1,1,2,2};
cout << majorityElement(nums) << endl; // 2
}
``````
``````Output:
3
2
``````

#### Complexity

• Runtime: `O(n)`, where `n = nums.length`.

• Extra space: `O(1)`.

### Modern C++ notes

In the code of Solution 3, the partial sorting algorithm `std::nth_element` will make sure for all indices `i` and `j` that satisfy `0 <= i <= mid <= j < nums.length`,

``````nums[i] <= nums[mid] <= nums[j].
``````

In other words, `nums[mid]` divides the array `nums` into two groups: all elements that are less than or equal to `nums[mid]` and the ones that are greater than or equal to `nums[mid]`.

Those two groups are unsorted. That is why the algorithm is called partial sorting.

### References

Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.