Majority Element II Solution

Problem

Given an array of integers, find every element that appears more than one-third of the total number of elements. Return all such elements in any order.

Input: nums = [3, 2, 3]
Output: [3]
Explanation: 3 appears 2 times, which exceeds ⌊3/3⌋ = 1

A second example with two qualifying elements:

Input: nums = [1, 1, 1, 3, 3, 2, 2, 2]
Output: [1, 2]
Explanation: 1 and 2 each appear 3 times, which exceeds ⌊8/3⌋ = 2; 3 appears only 2 times and does not qualify

Intuition

Since each qualifying element must appear more than n/3 times, three such elements would together account for more than n appearances — impossible. So at most two elements can ever qualify. This bound is the key insight: instead of tracking frequencies for the entire array, we only need to track two "candidates" and eliminate them against other values.

Approach 1: Hash Map

Count how many times each element appears, then collect every element whose count strictly exceeds the floor of n/3.

Build a frequency map by scanning the array once.
Compute the threshold: threshold = n // 3.
Collect all elements whose count is strictly greater than the threshold.
Return the collected elements.

1def majorityElement(nums: list[int]) -> list[int]:
2    frequency = {}
3    for num in nums:
4        frequency[num] = frequency.get(num, 0) + 1
5
6    threshold = len(nums) // 3
7    return [num for num, count in frequency.items() if count > threshold]

Time: O(n) — one pass to build the map, one pass over the map to filter.
Space: O(n) — the frequency map holds up to n distinct elements in the worst case.

Approach 2: Boyer-Moore Voting (Optimal)

Since at most 2 elements can qualify, maintain exactly 2 candidate/count pairs. When a new element matches neither candidate and both counts are positive, cancel one vote from each candidate — the true majority elements survive this cancellation. Verify the survivors in a second pass.

Initialize two candidates and their counts to zero/null.
For each element: if it matches a candidate, increment that count; else if a candidate's count is zero, adopt this element as that candidate; else decrement both counts.
Reset both counts to zero for a fresh pass.
Count how many times each surviving candidate actually appears.
Return candidates whose verified count strictly exceeds n // 3.

1def majorityElement(nums: list[int]) -> list[int]:
2    candidate1, candidate2 = None, None
3    count1, count2 = 0, 0
4
5    for num in nums:
6        if num == candidate1:
7            count1 += 1
8        elif num == candidate2:
9            count2 += 1
10        elif count1 == 0:
11            candidate1, count1 = num, 1
12        elif count2 == 0:
13            candidate2, count2 = num, 1
14        else:
15            count1 -= 1  # cancel one vote from each candidate
16            count2 -= 1
17
18    # Voting survivors are not guaranteed majority elements — must verify
19    count1, count2 = 0, 0
20    for num in nums:
21        if num == candidate1:
22            count1 += 1
23        elif num == candidate2:
24            count2 += 1
25
26    threshold = len(nums) // 3
27    result = []
28    if count1 > threshold:
29        result.append(candidate1)
30    if count2 > threshold:
31        result.append(candidate2)
32    return result

Time: O(n) — two linear passes over the array.
Space: O(1) — only four integer variables regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Hash Map	O(n)	O(n)	Default choice; simpler to read and reason about
Boyer-Moore Voting	O(n)	O(1)	When constant extra memory is a hard constraint

Common Mistakes

Skipping the verification pass in Boyer-Moore — the two candidates after the voting phase are NOT guaranteed to appear more than n/3 times; they are only the values that weren't fully cancelled. A second counting pass is mandatory to filter out false candidates.
Using ≥ instead of > for the threshold — "more than ⌊n/3⌋" is strictly greater; for n=6 the threshold is 2, and an element with exactly 2 occurrences does not qualify.
Wrong order in the Boyer-Moore if-chain — always check num == candidate before checking count == 0; if you check count == 0 first, you can accidentally assign both candidates to the same value when count is zero but the element matches the existing candidate.
Assuming the result always has two elements — inputs like [1, 2, 3] return an empty list (each element appears once, which is not more than ⌊3/3⌋ = 1), and [1, 1, 2, 3] returns [1] only.
Applying the single-candidate algorithm from Majority Element — the n/2 version tracks one candidate and always produces exactly one result; using it here would miss the second qualifying element whenever two exist.

Majority Element II — Solution