Solution: Majority Element

Statement#

Given an array, nums, having $n$ integers, return the majority element. An element will be considered a majority element if it occurs more than $⌊n / 2⌋$ times in the array.

Note: It is safe to assume that the majority element always exists in the array.

Constraints

• $n ==$ nums.length
• $1\leq n\leq 5* 10^4$
• $−10^9 \leq$ nums[i] $\leq10^9$

Solution#

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach#

A naive approach to solve this problem is to traverse the nums array by using a nested loop. This approach traverses the array for each element to count its occurrences. An element, whose count surpasses half of the array’s length, is returned as the result.

We indeed got our desired output. However, this approach is computationally expensive, especially for large arrays, because it requires iterating over the array repeatedly, which results in a time complexity of $O(n^2)$, where $n$ is the number of elements in the nums array.

Let’s try to devise some optimized approach that costs us less than this highly computationally expensive solution.

Optimized approach using knowing what to track#

An optimized approach to solve this problem is to keep track of the occurrences of the elements using the hash map. We iterate over nums and store the count of occurrences of each element in the hash map records. After effectively storing the frequency of each number, we return the element with the highest frequency as it will be the majority element.

Let’s look at the illustration to get a better understanding of the solution.

Let’s implement the algorithm as discussed above:

Solution summary#

1. Create a hash map, records, to store the frequencies of each element in the nums array.

2. Iterate through each element in nums and update its frequency in the records accordingly.

3. Return the element with the highest frequency.

Time complexity#

The time complexity of this solution is $O(n)$, where $n$ is the number of elements in nums. This is because the for loop takes $O(n)$ time to store the count of occurrences of each element in the hash map, and then finding the element with the highest count also takes $O(n)$ time. This leads to the total time complexity of $O(n + n)$, which simplifies to $O(n)$.

Space complexity#

In an array of length $n$, there can be at most $n$ distinct values. However, since nums is guaranteed to have a majority element, that means that $⌊n/2⌋+1$ are exactly the same elements. This implies that the hash map will hold a maximum of $n - ⌊n/2⌋$ elements, which will require $O(n)$ space. Therefore, the space complexity of this solution is $O(n)$.

Can we do better?#

Another more optimized approach is Boyer-Moore’s voting algorithm. This algorithm uses two variables to keep track of the majority element as it iterates through the array. The algorithm uses the fact that the majority element, by definition, occurs more frequently than any other element to cancel out the counts of non-majority elements. By canceling out all occurrences of elements that are not the majority element, this algorithm is able to identify the majority element in a single pass through the array. It has a time complexity of $O(n)$ and a space complexity of $O(1)$, making it a highly efficient solution to this problem.