Majority Element II LeetCode: Extended Boyer-Moore for n/3

Majority Element II (LeetCode #229) is a natural extension of the classic Majority Element problem. Instead of finding the single element that appears more than n/2 times, the majority element ii leetcode problem asks you to find all elements that appear more than n/3 times. The twist is that you still need to solve it in O(1) space.

If you already know Boyer-Moore Voting from Majority Element (#169), this problem is the perfect next step. The core insight is the same — use a voting mechanism to eliminate non-majority candidates — but now you track two candidates instead of one. It is the same elegant technique operating at a harder level.

By the end of this walkthrough, you will understand why at most two elements can appear more than n/3 times, how to extend Boyer-Moore with two candidates and two counters, and why a verification pass is essential. This is one of the best problems for learning how to generalize algorithms to harder variants.

The problem gives you an integer array of size n and asks you to find all elements that appear more than n/3 times. Return them as a list. The key constraint is that you should solve it in O(n) time and O(1) space — which rules out hash maps and sorting.

The mathematical insight is critical here. At most 2 elements can appear more than n/3 times. Think about it: if three elements each appeared more than n/3 times, their combined count would exceed n, which is impossible. This constraint is what makes O(1) space possible — you only need to track 2 candidates.

For example, in [3,2,3] the answer is [3] because 3 appears twice out of 3 elements (2 > 3/3 = 1). In [1,2] both 1 and 2 appear once each out of 2 elements (1 > 2/3 = 0.67), so the answer is [1,2]. In [1] the answer is [1]. The result can have zero, one, or two elements.

The leetcode 229 solution uses an extended version of Boyer-Moore Voting. Instead of one candidate and one count, you maintain two candidates (candidate1, candidate2) and two counts (count1, count2). The logic follows the same voting principle but with an extra slot.

For each element in the array, check three conditions in order. First, if the element matches candidate1, increment count1. Second, if the element matches candidate2, increment count2. Third, if count1 is zero, set candidate1 to the current element and count1 to 1. Fourth, if count2 is zero, set candidate2 to the current element and count2 to 1. If none of these conditions apply — meaning the element matches neither candidate and both counts are positive — decrement both count1 and count2.

The decrement step is where the magic happens. When you encounter an element that matches neither candidate, you are effectively saying "this element cancels out one vote from each candidate." After processing the entire array, the two candidates that survive are the only possible majority elements. But they are not guaranteed to be valid — you must verify them.

This is the most important difference between Majority Element I and Majority Element II. In the original problem (#169), the problem guarantees that a majority element exists. With that guarantee, the single surviving candidate is always correct. No verification needed.

In Majority Element II, there is no such guarantee. The array might have zero, one, or two elements appearing more than n/3 times. The boyer moore extended algorithm can produce false candidates — elements that survived the voting process but do not actually exceed the n/3 threshold. This happens when the array has no true majority elements or only one.

The fix is simple: after the first pass identifies two candidates, run a second pass through the array and count the actual occurrences of each candidate. Only include a candidate in the result if its actual count exceeds n/3. This verification pass adds O(n) time but keeps the overall complexity at O(n) time and O(1) space.

The two candidates voting approach translates to clean code in any language. Initialize candidate1 and candidate2 to any value (commonly 0) and both counts to 0. Loop through the array applying the four conditions described above. The order of conditions matters — always check for matches before checking for zero counts.

After the first pass, reset both counts to 0 and loop through the array again. Count exact occurrences of candidate1 and candidate2. If candidate1 appears more than n/3 times, add it to the result. Do the same for candidate2, but make sure it is different from candidate1 to avoid duplicates. Return the result list.

The time complexity is O(n) for two linear passes. The space complexity is O(1) because you only store two candidates and two counts, regardless of input size. This is the optimal solution that interviewers expect for the majority element n/3 times problem.

When the array has fewer than 3 elements, every element automatically appears more than n/3 times. An array of size 1 like [5] returns [5]. An array of size 2 like [1,2] returns [1,2]. The algorithm handles these naturally, but they are worth mentioning in an interview.

When exactly one element exceeds n/3 — like [1,1,1,2,3,4] where 1 appears 3 times out of 6 (3 > 2) — the result has a single element. When two elements exceed n/3 — like [1,1,2,2,3] where both 1 and 2 appear twice out of 5 (2 > 1.67) — the result has two elements. When no element exceeds n/3 — like [1,2,3] where each appears once out of 3 (1 is not > 1) — the result is an empty list.

A subtle edge case is when both candidates end up as the same value. This can happen depending on your initialization. Always check that candidate1 and candidate2 are different before counting, or handle duplicates when building the result. Most clean implementations avoid this by checking matches before zero-count reassignment.

Majority Element II is a masterclass in extending algorithms to harder variants. The jump from one candidate to two candidates is small in code but significant in understanding. It teaches you to think about algorithm generalization — if Boyer-Moore works for n/2 with one candidate, how does it scale to n/3 with two candidates? And by extension, n/k with k-1 candidates.

This problem also teaches the importance of verification passes. In the original Majority Element, guarantees made verification unnecessary. Here, the lack of guarantees forces you to add a second pass. Recognizing when algorithm assumptions change — and what safeguards to add — is a skill that separates good candidates from great ones in coding interviews.

If you found this majority element ii leetcode walkthrough helpful, YeetCode flashcards can help you drill the Boyer-Moore pattern and its extensions through spaced repetition. Understanding how one algorithm generalizes to harder variants is exactly the kind of deep pattern recognition that makes interview problems feel familiar instead of frightening.