Introduction

The majority-element problem asks whether one value appears more than half the time in an array. It is a classic algorithm question because the cleanest optimal solution runs in linear time while using constant extra space. The important detail is whether a majority element is guaranteed to exist.

What Makes an Element a Majority

For an array of length n, a majority element appears strictly more than n / 2 times. That means there can be at most one such value.

Examples:

• '[2, 2, 1, 2] has majority element 2'
• '[1, 2, 3, 4] has no majority element'

That second case matters because some interview problems promise a majority, while production code often cannot assume one.

Counting With a Dictionary

The easiest solution is frequency counting:

1def majority_element_count(nums):
2    counts = {}
3    threshold = len(nums) // 2
4
5    for value in nums:
6        counts[value] = counts.get(value, 0) + 1
7        if counts[value] > threshold:
8            return value
9
10    return None
11
12
13print(majority_element_count([2, 2, 1, 1, 1, 2, 2]))
14print(majority_element_count([1, 2, 3, 4]))

This runs in O(n) time and is very readable. The tradeoff is O(n) extra space in the worst case.

That is often acceptable in real applications. If clarity matters more than memory minimization, this is a strong default choice.

Boyer-Moore Voting Algorithm

If you want the classic optimal-space algorithm, use Boyer-Moore. The idea is to cancel different values against each other until a candidate remains.

1def majority_candidate(nums):
2    candidate = None
3    count = 0
4
5    for value in nums:
6        if count == 0:
7            candidate = value
8            count = 1
9        elif value == candidate:
10            count += 1
11        else:
12            count -= 1
13
14    return candidate
15
16
17print(majority_candidate([2, 2, 1, 1, 1, 2, 2]))

This gives:

• time complexity: O(n)
• extra space: O(1)

That is why it is the standard interview answer.

Why Boyer-Moore Works

Imagine pairing off one occurrence of the current candidate with one occurrence of a different value. If a true majority exists, it has enough occurrences to survive all possible cancellations.

For example, in [2, 2, 1, 1, 1, 2, 2], the non-2 values can cancel some 2 values, but not all of them. The majority element remains as the final candidate.

The important limitation is that Boyer-Moore only guarantees a correct candidate when a majority actually exists. Without that guarantee, you still need a verification step.

Verifying the Candidate

When the input may not contain a majority element, do a second pass:

1def majority_element(nums):
2    candidate = majority_candidate(nums)
3    if candidate is None:
4        return None
5
6    actual_count = sum(1 for value in nums if value == candidate)
7    return candidate if actual_count > len(nums) // 2 else None
8
9
10print(majority_element([2, 2, 1, 1, 1, 2, 2]))
11print(majority_element([1, 2, 3, 4]))

The second pass keeps the total time complexity at O(n). Two linear passes are still linear.

Sorting as an Alternative

Sorting also works. If a majority element exists, it must occupy the middle position after sorting:

1def majority_element_sorted(nums):
2    if not nums:
3        return None
4
5    sorted_nums = sorted(nums)
6    candidate = sorted_nums[len(nums) // 2]
7    count = sum(1 for value in nums if value == candidate)
8    return candidate if count > len(nums) // 2 else None
9
10
11print(majority_element_sorted([3, 3, 4, 2, 3, 3, 5]))

This is easy to reason about, but sorting costs O(n log n), so it is usually not the best answer if linear time is available.

Common Pitfalls

The biggest mistake is returning the Boyer-Moore candidate without verification when the input may not contain a majority element. The algorithm still returns some candidate, but that candidate may not be correct.

Another mistake is confusing a plurality with a majority. The most frequent value is not enough unless it appears more than half the time.

People also forget empty-array handling. Decide whether your function should return None, raise an exception, or rely on an input guarantee.

Finally, do not dismiss the dictionary approach just because it uses extra space. In production code, simpler logic is often worth that cost.

Summary

• A majority element appears more than half the time in the array.
• Dictionary counting is straightforward and still runs in linear time.
• Boyer-Moore finds a candidate in O(n) time with O(1) extra space.
• If a majority is not guaranteed, verify the Boyer-Moore candidate with a second pass.
• Sorting also works, but it is slower than the linear-time approaches.