229. Majority Element II
Model: qwen3.5:9b
Topics: Array
FAANG asked: 1
Acceptance rate: 39.0%
Problem Breakdown
We need to identify all integers in an array that appear more than times, where is the length of the array.
Key constraints and implications:
- Frequency Threshold: Since we are looking for elements appearing strictly greater than one-third of the total size, there can be at most two such elements in any valid input (because if three distinct numbers each appeared > n/3 times, their sum would exceed , which is impossible). This gives us a hint that our solution only needs to track up to 2 candidates.
- Input Range: Integers range from to . We cannot use an array-based frequency map (bucket sort style) because the values are too sparse and large; we must rely on hashing or a different algorithmic approach.
- Edge Cases:
n = 1: The single element is trivially > n/3.- No majority elements: We might find candidates during traversal that don’t actually meet the threshold, so verification is mandatory.
Intuition
A naive approach would be to use a Hash Map (Counter) to count every unique number and then filter those with count > len(nums)//3.
- Time Complexity: for counting + where is the number of unique elements. In worst case, this is still acceptable time-wise ().
- Space Complexity: However, in a real-world production environment or strict memory-constrained interview setting (like LeetCode’s follow-up), storing every distinct element uses space. The interviewer specifically asked for the “Follow-up” solution: linear time and O(1) extra space.
To achieve space without sorting, we can adapt Boyer-Moore Voting Algorithm.
- For a majority > n/2 (one candidate), we maintain one counter and cancel out pairs of different elements until only the potential winner remains.
- For a majority > n/3 (two candidates), there are at most two “winners”. We can extend this logic to track two counters (
count1,count2) and their corresponding values (cand1,cand2). - When we encounter an element:
- If it matches a candidate, increment that counter.
- If neither match exists (or both counts are 0), adopt the current number as one of the candidates if there is room in our “slots”.
- Otherwise, decrement all counters to simulate canceling out non-majority elements against each other.
Approach
- First Pass (Candidate Identification): Iterate through
numsonce. Maintain two candidate slots and their vote counts.- If the current number matches a candidate’s value, increment that count.
- Else if it doesn’t match any active candidate: decrement both counters to simulate “canceling out” votes against non-majority elements. However, we must be careful not to overwrite candidates with valid values while their counts are zero unless necessary. A cleaner logic is: If a counter hits 0, replace that slot’s candidate with the current number and reset count to 1 (unless it matches an existing active candidate).
- Second Pass (Verification): The voting algorithm guarantees finding potential candidates if they exist > n/3 times. However, because we decrement counts arbitrarily during traversal, a non-majority element might survive as a “candidate” with a positive count at the end of pass one. We must iterate through
numsagain to calculate the actual frequency of these two survivors and check against .- If an element’s true count > , add it to results.
Complexity Analysis
- Time: . We traverse the array twice (once for voting, once for counting). Both are linear scans.
- Space: auxiliary space. We only store two candidate values and their counts plus a few variables for verification. The output list is not counted in space complexity as it’s required by definition of return value.
Solution
class Solution:
def majorityElement(self, nums):
# Step 1: Find candidates using generalized Boyer-Moore Voting Algorithm
cand1 = None
count1 = 0
cand2 = None
count2 = 0
for num in nums:
if count1 > 0 and num == cand1:
count1 += 1
elif count2 > 0 and num == cand2:
count2 += 1
else:
# If current number doesn't match any candidate, decrement counts.
# However, we need to handle the case where a slot is empty (count=0).
if count1 == 0:
cand1 = num
count1 = 1
elif count2 == 0:
cand2 = num
count2 = 1
else:
# Both slots active and no match -> cancel out votes for both
count1 -= 1
count2 -= 1
# Step 2: Verify candidates against the threshold n/3
result = []
if cand1 is not None or nums[0] == cand1:
# Note: We need to handle initialization carefully.
# If we used 'None' as placeholder, checking count > 0 ensures validity?
# Actually, standard practice checks the actual counts found in pass 2.
# Let's refine verification logic for clarity and correctness
if cand1 is not None:
c = nums.count(cand1)
if c > len(nums) // 3:
result.append(cand1)
if cand2 is not None and cand2 != cand1: # Ensure we don't add duplicate if they are same value (rare but possible logic-wise)
c = nums.count(cand2)
if c > len(nums) // 3:
result.append(cand2)
return result
Wait, the verification code above has a flaw in initialization handling. If cand1 is initialized to None but we never set it (e.g. input [0]), logic needs care. Let’s rewrite for robustness: use placeholders that won’t conflict with valid inputs or handle counts strictly > 0 before checking value equality during verification? Actually, simpler approach in Python: just check if count1 > 0. But wait, the voting algorithm might leave a candidate with count=0 at end of pass. We should only verify candidates where we actually assigned them (or initialized).
Better logic for Step 2 inside code block to ensure it’s clean and correct without relying on ‘None’ ambiguity:
# Verification Phase
result = []
if cand1 is not None or count1 > 0:
# Wait, checking `cand1` against input values requires care.
# If we initialized with a value that isn't in array? No, we only set cand when count=0->set=num.
pass
Let’s simplify the code block to be production-ready and clean:
Edge Cases Handled
- Single Element (
n=1): The loop sets one candidate withcount=1. Verification confirms it is > 0//3 (which is 0). Returns[num]. Correct. - No Majority Elements: Candidates might be found, but their actual counts will fail the threshold check in Step 2. Result remains empty list.
- Two Distinct Majorities (
[1, 2]): Both slots get filled and maintained (counts never hit zero). Verification confirms both > n/3. Returns[1, 2]. Correct. - Duplicate Values: The logic handles duplicates naturally by incrementing counts when
num == cand.