NeetCode #109LC-229MediumArrays & HashingNC 250
← Back to All Problems#109 · #229 · Majority Element II(多数元素 II)
📌 Problem Statement & Constraints
Given an integer array
nums of size n, find all elements that appear more than n / 3 times. Constraints: 1 <= n <= 5 * 10^4, -10^9 <= nums[i] <= 10^9. The solution must run in O(n) time and use O(1) space.💡 Core Algorithmic Approaches
- At most two elements can appear more than
n / 3times, because three such elements would already exceedn. - Extend Boyer-Moore voting to two candidates. Maintain
c1, n1andc2, n2. - For each element
x: ifx == c1incrementn1; else ifx == c2incrementn2; else ifn1 == 0adoptxasc1; else ifn2 == 0adoptxasc2; else decrement both counters. - Unlike the majority case, existence is not guaranteed, so a second pass must count the occurrences of each candidate and filter those exceeding
n / 3.
💻 Benchmark Python3 Implementation
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
c1 = c2 = None
n1 = n2 = 0
for x in nums:
if x == c1:
n1 += 1
elif x == c2:
n2 += 1
elif n1 == 0:
c1, n1 = x, 1
elif n2 == 0:
c2, n2 = x, 1
else:
n1 -= 1 # cancel one vote from each candidate
n2 -= 1
# mandatory verification: existence is not guaranteed here
res = []
for c in (c1, c2):
if c is not None and nums.count(c) * 3 > len(nums):
res.append(c)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass for voting plus one pass for verification (nums.count runs twice, each O(n)).
💾 Space Complexity
O(1): four scalar variables. A Counter would be O(n) space and is the naive baseline.
⚠️ Interview Pitfalls & Follow-ups
- Skipping the verification pass: the algorithm only guarantees that any element exceeding n/3 must be one of the two candidates -- it does not guarantee the candidates qualify.
- Forgetting the
n1 == 0/n2 == 0branches: without them, an element can never become a new candidate once both slots are taken. - Decrementing only one counter in the cancel branch: both must be decremented; this is what makes the two-candidate version work.
- Allowing the same value to occupy both candidate slots: initialising them to
Noneand usingelifchains prevents this. - Assuming exactly two answers: the result can contain zero, one or two elements.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.