Majority Element II

The “Majority Element II” problem asks you to find all elements in an integer array that appear more than one-third of the time. Unlike the classic majority element problem that looks for an element occurring more than half the time, this version can have up to two valid answers. Your task is to return those elements, and if none exist, return an empty result.

This problem is deceptively simple to state but requires careful reasoning to solve efficiently. The one-third threshold creates a very specific mathematical constraint that the optimal solution relies on.

Why counting frequencies is not the intended solution

A direct approach would be to count frequencies using a hash map and then collect elements whose counts exceed one-third of the array length. This is correct, but it uses extra space proportional to the number of distinct elements.

The interesting part of this problem is that it can be solved using constant extra space by leveraging a voting-based idea. The goal is to identify potential candidates without tracking every frequency explicitly, then verify those candidates in a final pass.

The key constraint: there can be at most two answers

The most important observation is structural. If an element appears more than one-third of the time, then there cannot be three such distinct elements. If three different elements each appeared more than one-third of the time, their total occurrences would exceed the size of the array, which is impossible.

This constraint is why the problem allows a constant-space solution. Instead of tracking potentially many frequencies, you only ever need to track up to two candidates.

Want to explore more coding problem solutions? Check out the Minimum Cost for Tickets and Reconstruct Itinerary.

Extending the voting idea to two candidates

The solution is based on a generalized voting process. In the classic version, you track one candidate and a counter. Here, you track two candidates and two counters.

As you scan the array, matching values reinforce their candidate. When you encounter a value that matches neither candidate, and both counters are nonzero, you reduce both counters. Conceptually, this “cancels out” a group of three different values: the new value and one occurrence of each candidate. This cancellation is safe because removing such a triple cannot eliminate a true one-third majority, since a real majority would still remain dominant after repeated cancellations.

Why cancellation preserves true majorities

The cancellation logic works because the one-third threshold implies resilience. An element that appears more than one-third of the time cannot be fully eliminated by repeatedly removing balanced groups of distinct elements. It will continue to show up often enough to remain as a candidate by the end of the pass.

At the same time, elements that do not meet the threshold are vulnerable to cancellation and tend to be removed from candidacy over time. This is why the algorithm narrows the field down to at most two plausible contenders.

Why you still need a verification pass

After the first scan, the two tracked candidates are only potential answers. The voting process guarantees that any valid answer must be among them, but it does not guarantee that both candidates actually exceed the one-third threshold.

This is why a second pass is required. You count how many times each candidate appears and include it in the output only if it truly exceeds one-third of the array length. This verification step is the difference between “possible candidates” and “correct final result.”

Time and space complexity considerations

The algorithm runs in linear time because it scans the array a constant number of times. It uses constant extra space because it stores only two candidates and two counters, plus a small amount of additional tracking during verification.

This efficiency is exactly what makes the approach attractive. You get the correctness of frequency counting without the memory cost of storing a full frequency map.

Why this problem is popular in interviews

Majority Element II is commonly used in interviews because it tests whether candidates can spot hidden constraints and exploit them. Many people default to hash maps, which is fine, but the optimal approach demonstrates deeper algorithmic reasoning.

It also tests whether you understand why a clever first pass needs a second pass for validation, which is a subtle but important concept in streaming and candidate-selection algorithms.

What this problem teaches beyond majority elements

Beyond this specific problem, the generalized voting approach teaches a broader lesson about candidate reduction. When the problem guarantees a small upper bound on the number of valid answers, you can often design constant-space algorithms that filter candidates first and verify later.

If you can clearly explain why there can be at most two answers, how cancellation works, and why verification is necessary, you demonstrate strong algorithmic intuition. That depth of understanding makes “Majority Element II” an excellent exercise in constraint-driven optimization and constant-space reasoning.