169. Majority Element

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”.