LeetCode #229 Medium

Majority Element II

Return all elements that appear more than ⌊n/3⌋ times. There can be at most two such elements.

arrayboyer-moorecounting

02

Intuition

💡

If three different values each appeared more than n/3 times, their counts would exceed n — impossible. So the answer holds at most two elements, and we can run Boyer-Moore voting with two candidates at once.

03

Approach

1

First, why the answer has at most two elements

This is the crucial counting argument. If three different values each appeared more than n/3 times, their combined count would exceed 3 × (n/3) = n — impossible in an array of length n. So at most two values can clear the n/3 bar. That bound is what makes a constant-space solution possible: we only ever need to track two candidates at once.

2

Run Boyer-Moore with two slots

Generalize the single-candidate vote to two. Keep candidates c1, c2 with counters k1, k2. A value matching either candidate bumps that counter. A value matching neither, when both counters are non-zero, decrements both — that's the three-way cancellation (one of each candidate against the newcomer) that mirrors the n/3 threshold, just as the n/2 problem cancelled two at a time. Empty slots adopt new candidates.

3

Voting narrows; a second pass verifies

Voting only guarantees that if answers exist they're among c1, c2 — it does not prove either actually qualifies. For example [1,2,3] leaves candidates that each appear only once. So make a second pass that counts the real frequency of each survivor and keeps only those strictly above n/3. This verification is order-independent, so it cleans up any transient mistakes the vote made mid-scan. O(n) time, O(1) space.

04

Solution & live demo

python

▶1class Solution:
▶2    def majorityElement(self, nums):
▶3        cand1 = cand2 = None
▶4        count1 = count2 = 0
▶5        for x in nums:
▶6            if cand1 is not None and x == cand1:
▶7                count1 += 1
▶8            elif cand2 is not None and x == cand2:
▶9                count2 += 1
▶10            elif count1 == 0:
▶11                cand1, count1 = x, 1
▶12            elif count2 == 0:
▶13                cand2, count2 = x, 1
▶14            else:
▶15                count1 -= 1
▶16                count2 -= 1
▶17        result = []
▶18        for c in (cand1, cand2):
▶19            if c is not None and nums.count(c) > len(nums) // 3:
▶20                result.append(c)
▶21        return result

05

Edge cases

No element exceeds n/3, e.g. [1,2,3]

The mandatory verification pass discards both suspects, returning an empty list.

A single dominant value

One slot fills, the other stays empty; verification keeps just the real majority.

Order-dependent vote noise

Counters can swap candidates mid-scan, but the final verification is order-independent and corrects any transient mistake.

06

Complexity

Time

O(n)

Space

O(1)

Voting pass plus up to two verification counts.