Majority Element II

Majority Element II

What is this problem about?

The Majority Element II problem is an evolution of the classic Majority Element question. Given an integer array of size N, you need to find all elements that appear strictly more than ⌊N / 3⌋ times. Unlike the first problem, the answer could be a list containing zero, one, or two elements.

Why is this asked in interviews?

This question takes a known algorithm (Boyer-Moore Voting) and stretches it. Interviewers ask it to see if a candidate truly understands the underlying mathematical principles of the voting algorithm, or if they just memorized the code for part I. It evaluates your ability to manage multiple concurrent states and logically deduce maximums (since an array can only have at most two elements appearing $> N/3$ times).

Algorithmic pattern used

This problem uses the Extended Boyer-Moore Voting Algorithm. Because we are looking for elements appearing more than N/3 times, there can be at most two such elements. We maintain two candidate variables and two count variables. We iterate through the array, assigning/incrementing candidates. Crucially, if the current number doesn't match either candidate, we decrement both counts. Finally, a second pass is strictly required to verify that the final candidates actually appear $> N/3$ times.

Example explanation

Array: [1, 1, 1, 3, 3, 2, 2, 2] ($N=8$, target $> 2$). Pass 1:

• 1s: cand1 = 1, count1 = 3.
• 3s: cand2 = 3, count2 = 2.
• 2: Matches neither! Decrement both. count1 = 2, count2 = 1.
• 2: Matches neither! Decrement both. count1 = 1, count2 = 0.
• 2: count2 is 0. cand2 = 2, count2 = 1. Final candidates: 1 and 2.

Pass 2 (Verification):

• Count occurrences of 1 in array: 3. ($3 > 2$). Valid!
• Count occurrences of 2 in array: 3. ($3 > 2$). Valid! Result: [1, 2]. (Note: 3 was eliminated organically because its count dropped to 0).

Common mistakes candidates make

The most common and devastating mistake is skipping the second verification pass. In the original Majority Element problem, the prompt guarantees the majority element exists, so whatever is left at the end is the answer. In Part II, there is no guarantee! If the array is [1, 2, 3], your algorithm might spit out 1 and 2, but neither appears $> N/3$ times. You must re-count the candidates.

Interview preparation tip

When implementing the Extended Boyer-Moore algorithm, the order of your if/else if statements is critical. Always check for matches with candidate1 and candidate2 FIRST, before checking if count1 == 0 or count2 == 0. If you assign a new candidate before checking matches, you might accidentally assign the same number to both candidate slots, destroying the logic.