In the world of algorithms, one common problem that manifests in interview scenarios and technical assessments is finding the element that appears more than $n/2$ times in an array of size $n$. This element is commonly known as the "majority element." The problem can be solved using different approaches, each with varying complexities. This article presents several methods to solve this problem, along with a technical explanation and examples for each, summarized in a table towards the end.

Problem Definition

Given a non-empty array of integers, find the majority element. The majority element is the element that appears more than $\lfloor n / 2 \rfloor$ times, where $n$ is the length of the array. It is assumed that the array always contains a majority element.

Example

Consider the array [2, 2, 1, 1, 1, 2, 2] . The majority element here is 2 , as it appears 4 times out of 7 elements, which is more than $7/2 = 3.5$ times.

Approach 1: Hash

Map (Frequency Count)

Algorithm:

1. Create an empty hash map (or dictionary).
2. Traverse the array, counting the occurrence of each element.
3. As soon as an element’s count exceeds $n/2$, return that element.

Complexity:

• Time Complexity: $O(n)$, where $n$ is the length of the array.
• Space Complexity: $O(n)$ in the worst case if all elements are unique.

Example:

For the array [2, 2, 1, 1, 1, 2, 2] , the hash map would be:

• 2 : 4 occurrences
• 1 : 3 occurrences

Element 2 is found to be the majority element since it first reaches count 4.

Approach 2: Sorting

Algorithm:

1. Sort the array.
2. The element at the middle index ($n/2$) in the sorted array is the majority element.

Complexity:

• Time Complexity: $O(n \log n)$, due to sorting.
• Space Complexity: $O(1)$ if the sort is in-place, otherwise $O(n)$.

Example:

For the array [2, 2, 1, 1, 1, 2, 2] , sorting gives us [1, 1, 1, 2, 2, 2, 2] .

• Element at index 3 (i.e., $7/2$) is 2 , the majority element.

Approach 3: Boyer-Moore Voting Algorithm

Algorithm: This algorithm uses a counter initialized to zero and iterates over the array. It maintains a candidate for the majority element and the rule for toggling the candidate is:

• Choose the current element as a potential candidate when the counter is zero.
• If the current element matches the candidate, increment the counter.
• Otherwise, decrement the counter.

Complexity:

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

Example:

For the array [2, 2, 1, 1, 1, 2, 2] :

• Starting with candidate 2 and count 0 .
• Increment count for first two 2 s.
• Decrement for three 1 s, making count 0 after third 1 .
• New candidate becomes 2 with remaining 2 s solidifying it as the majority element.

Key Points Summary

Additional Considerations

Edge Cases

1. Single-element arrays: The sole element is trivially the majority element.
2. Arrays with all identical elements: Every element is the majority element.
3. Even-sized arrays: The assumption guarantees a majority element exists, handling cases naturally.

Practical Applications

The concept of finding the majority element is a foundational problem that can be applied in databases, machine learning voting ensembles, and distributed systems where consensus needs to be achieved.

The efficient Boyer-Moore Voting algorithm is particularly elegant due to its linear time complexity and constant space usage, making it an optimal and robust solution for this problem. However, practical implementation can depend on additional factors like data structure preferences and computational resource constraints.