Majority Element LeetCode: Boyer-Moore Voting in O(1) Space

Some LeetCode problems have solutions so clean they feel like magic. Majority Element (#169) is one of them. The problem asks you to find the element that appears more than n/2 times in an array — and while hash maps and sorting both work, the optimal solution is Boyer-Moore Voting, an algorithm that finds the answer in a single pass with zero extra space.

The majority element LeetCode problem is classified as Easy, but the optimal approach teaches a technique that most candidates never learn. Boyer-Moore Voting was published in 1981 and remains one of the most elegant algorithms in computer science. Once you see how it works, you will never forget it.

In this walkthrough, you will progress through three approaches — hash map, sorting, and Boyer-Moore Voting — so you understand not just the optimal solution but the thinking that gets you there. This is exactly the kind of approach progression interviewers love to see.

The problem statement is straightforward: 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 the majority element always exists in the array.

That guarantee is critical. In an array of 7 elements, the majority element appears at least 4 times. In an array of 100 elements, it appears at least 51 times. This means the majority element always occupies more than half of the array — a property that Boyer-Moore Voting exploits brilliantly.

Example: given [2, 2, 1, 1, 1, 2, 2], the majority element is 2 because it appears 4 times out of 7. Given [3, 3, 4], the majority element is 3. The constraint that the majority element is guaranteed to exist simplifies all three approaches significantly.

The most intuitive approach is to count how many times each element appears using a hash map. Iterate through the array, incrementing the count for each element. Once any element's count exceeds n/2, return it immediately.

This approach runs in O(n) time because you visit each element once and hash map operations are O(1) on average. However, it uses O(n) space for the hash map — in the worst case, you store counts for n/2 distinct elements before finding the majority.

The hash map approach is perfectly valid in an interview and demonstrates solid problem-solving instinct. But when an interviewer asks "can you do better on space?", you need to know the next two approaches.

Here is a clever observation: if you sort the array, the majority element must be at index n/2. Why? Because the majority element occupies more than half of the array. No matter where it starts in the sorted order, it must stretch across the middle position.

Think about it visually. If the majority element is the smallest value, it fills positions 0 through at least n/2. If it is the largest, it fills positions starting before n/2 through n-1. Either way, position n/2 is always covered. Just sort and return nums[n/2].

Sorting trades space for time in an interesting way. Most sorting algorithms use O(log n) stack space, which is better than O(n), but the time complexity jumps to O(n log n). This is a valid tradeoff to discuss in an interview.

Boyer-Moore Voting is the optimal solution to the majority element problem. It uses only two variables — a candidate and a count — and finds the majority element in a single pass. No hash map, no sorting, no extra memory beyond two integers.

The algorithm works like an election. Walk through the array maintaining a current candidate and a running count. For each element: if the count is zero, adopt the current element as the new candidate. If the current element matches the candidate, increment the count. If it differs, decrement the count. After processing all elements, the candidate is the majority element.

That is the entire algorithm. Four lines of logic that solve the problem in O(n) time and O(1) space. The simplicity is what makes Boyer-Moore Voting one of the most celebrated algorithms in computer science.

The intuition behind Boyer-Moore Voting is a cancellation argument. Imagine pairing each occurrence of the majority element with a different element. Since the majority element appears more than n/2 times, there are not enough other elements to cancel all of its occurrences. At least one "vote" for the majority element always survives.

When the count drops to zero, you are effectively saying "everything I have seen so far has cancelled out." But the majority element still has more remaining occurrences than all other elements combined in the unprocessed portion of the array. So no matter how many times the candidate resets, the true majority will eventually take over and hold the lead.

Walk through [2, 2, 1, 1, 1, 2, 2] step by step. Start with candidate=2, count=1. Next 2: count=2. Next 1: count=1. Next 1: count=0. Next 1: candidate=1, count=1. Next 2: count=0. Next 2: candidate=2, count=1. The final candidate is 2 — correct.

The key mathematical fact is this: if the majority element appears more than n/2 times, its count can never be fully reduced to zero by the remaining elements. The survivor of the cancellation process must be the majority element.

Majority Element is a perfect example of approach progression — moving from an obvious O(n) space solution through a sorting trick to an optimal O(1) space algorithm. Interviewers love seeing this kind of progression because it shows you can optimize under pressure, not just solve.

Boyer-Moore Voting is a standalone algorithm worth memorizing. It appears directly in interview questions and has variants for finding elements that appear more than n/3 times (LeetCode 229). Understanding the cancellation principle gives you a tool that no amount of hash map thinking can replace.

The pattern of tracking a candidate and a count also appears in stream processing, distributed systems, and data analysis where you need to find frequent items with limited memory. This is not just an interview trick — it is a fundamental algorithmic idea.

Practice this problem until Boyer-Moore feels automatic. YeetCode flashcards help you drill the algorithm and its edge cases through spaced repetition, so the four-line solution becomes second nature before your interview day.