Majority Element II — Extended Boyer-Moore Voting [LC 229]

Problem Statement#

Given an integer array nums, return all elements that appear more than n/3 times. The answer is guaranteed to have at most 2 elements.

Constraints:

• 1 <= nums.length <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

Input:  nums = [3,2,3]
Output: [3]

Input:  nums = [1,1,1,3,3,2,2,2]
Output: [1,2]

Why This Problem Matters#

LeetCode 229 extends the classic Majority Element (LC 169) — which uses one Boyer-Moore candidate — to two candidates. This is a FAANG-grade problem because it tests whether you can generalize an algorithm. Amazon, Google, and Microsoft ask it to verify that candidates understand both the original Boyer-Moore and the mathematical reason why at most n/3 threshold means at most 2 majority elements.

The O(1) space requirement rules out hash maps and sorting, forcing the elegant two-candidate voting approach. This problem is also a gateway to the general Boyer-Moore generalization: for threshold n/k, maintain k-1 candidates.

The Core Insight#

Mathematical fact: At most 2 elements can appear more than n/3 times (since 3 elements each appearing more than n/3 times would require more than n elements total).

Extended Boyer-Moore Voting:

1. Maintain two candidate-count pairs (c1, cnt1) and (c2, cnt2)
2. For each element:
   • If it equals c1 or c2, increment that count
   • Else if cnt1 == 0, replace c1 with this element, cnt1 = 1
   • Else if cnt2 == 0, replace c2 with this element, cnt2 = 1
   • Else decrement both cnt1 and cnt2 by 1 (cancel three distinct elements)
3. Verify both candidates with a second pass (the algorithm finds at most two candidates, not necessarily valid ones)

Visual Dry Run#

nums = [1,1,1,3,3,2,2,2]

Candidates: 1 and 2. Verify: 1 appears 3 times (3 > 8/3=2.67), 2 appears 3 times — both valid. Result: [1, 2]

Solution (Optimal)#

class Solution:
    def majorityElement(self, nums):
        c1, cnt1, c2, cnt2 = None, 0, None, 0
        for n in nums:
            if n == c1:
                cnt1 += 1
            elif n == c2:
                cnt2 += 1
            elif cnt1 == 0:
                c1, cnt1 = n, 1
            elif cnt2 == 0:
                c2, cnt2 = n, 1
            else:
                cnt1 -= 1
                cnt2 -= 1
        # Verify candidates
        return [c for c in (c1, c2) if c is not None and nums.count(c) > len(nums) // 3]

var majorityElement = function(nums) {
    let c1 = null, cnt1 = 0, c2 = null, cnt2 = 0;
    for (const n of nums) {
        if (n === c1) cnt1++;
        else if (n === c2) cnt2++;
        else if (cnt1 === 0) { c1 = n; cnt1 = 1; }
        else if (cnt2 === 0) { c2 = n; cnt2 = 1; }
        else { cnt1--; cnt2--; }
    }
    const n = nums.length;
    const res = [];
    if (c1 !== null && nums.filter(x => x === c1).length > Math.floor(n / 3)) res.push(c1);
    if (c2 !== null && nums.filter(x => x === c2).length > Math.floor(n / 3)) res.push(c2);
    return res;
};

Time: O(n) — two passes through the array Space: O(1) — four scalar variables only

Common Mistakes#

• Not verifying candidates after the voting phase — the algorithm finds at most two candidates but they may not actually be majority elements
• Missing the decrement step when neither candidate matches — must decrement both counts to cancel three distinct elements
• Checking >= n/3 instead of > n/3 — the problem asks for strictly more than n/3
• Forgetting that the output can be empty (if no element appears more than n/3 times)
• Assuming there are always exactly 2 answers — there can be 0, 1, or 2 majority elements

Interview Tips#

• Start with the mathematical insight: "at most 2 elements can exceed n/3 since 3*n/3 = n"
• Explain the cancellation: "when we decrement both, we're canceling 3 distinct elements — the majority elements survive this"
• Emphasize the verification step — many candidates forget this and get wrong answers
• For LC 169 (n/2 threshold), explain this is just the 1-candidate version of the same algorithm
• Mention the generalization: for n/k threshold, maintain k-1 candidates (Boyer-Moore generalization)

Follow-up Questions#

• What if the threshold is n/4? (Maintain 3 candidates — the k-1 generalization of Boyer-Moore)
• How does this compare to using a HashMap? (HashMap is O(n) time O(n) space — Boyer-Moore achieves O(1) space)
• Can you solve it in one pass instead of two? (Not without extra space — you need the verification second pass)
• What if you want the majority element that appears the most times (not just all above threshold)? (Use a regular HashMap and track max count)
• How do you handle negative numbers or large integers? (The algorithm handles any comparable values — no special handling needed)

Key Takeaways#

• LeetCode 229 is asked at Amazon, Google, and Microsoft — Extended Boyer-Moore voting with two candidates
• At most 2 elements can appear more than n/3 times — mathematical basis for using exactly two candidates
• The cancellation: when a new element matches neither candidate and both counts are positive, decrement both (cancel 3 distinct values)
• Always verify both candidates in a second pass — the voting phase identifies candidates, not guarantees
• Time O(n), Space O(1) — two passes with four scalar variables
• For Majority Element I (LC 169), the same algorithm with one candidate handles n/2 threshold
• Generalizes to n/k threshold with k-1 candidates — knowing this generalization impresses interviewers