LeetCode: 169. Majority Element

The Problem

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

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 * 104
• -109 <= nums[i] <= 109

The Solution

We opted for a simple approach using a for loop

int majorityElement(vector<int>& nums) {
	unordered_map<int, int> count;
	int n = ceil(nums.size() / 2.0);

	for(int i = 0; i < nums.size(); ++i) {
		++count[nums[i]];
		if(count[nums[i]] >= n) return nums[i];
	}

	return -1;
}

Let's break down the code step by step:

1. int majorityElement(vector<int>& nums) {: This line defines a function named majorityElement that takes a reference to a vector of integers (nums) as its parameter. The function returns an integer.
2. unordered_map<int, int> count;: Here, an unordered map named count is declared. This map will store the count of occurrences of each integer in the input vector.
3. int n = ceil(nums.size() / 2.0);: This line calculates the minimum threshold count required for an element to be considered a majority element. It is computed as half the size of the input vector, rounded up to the nearest integer.
4. for(int i = 0; i < nums.size(); ++i) {: This line starts a loop that iterates over each element of the input vector.
5. ++count[nums[i]];: Inside the loop, the code increments the count of the current element (nums[i]) in the count map.
6. if(count[nums[i]] >= n) return nums[i];: This condition checks if the count of the current element has reached or exceeded the minimum threshold required for it to be considered a majority element. If so, the function immediately returns the current element as the majority element.
7. return -1;: If the loop completes without finding a majority element, the function returns -1, indicating that there is no majority element in the input vector.