PPractick

The problem

A product survey lets users pick one favourite feature, and the team wants to highlight every feature chosen by more than a third of respondents. At most two features can clear that bar, since three features each with more than a third would add up to more than everyone. Extending Boyer–Moore voting to two candidates finds them in one pass with O(1) memory; a second pass then confirms which candidates really clear the threshold.

Example: [1, 1, 1, 3, 3, 2, 2, 2] → [1, 2].

Function signature

vector<int> majorityElement(const vector<int>& nums);  // all values appearing more than n/3 times, sorted

Test cases

Input nums	Output	Explanation
[3, 2, 3]	[3]	3 appears 2 > 1 times
[1]	[1]
[1, 2]	[1, 2]	Each appears 1 > 0 times
[1, 1, 1, 3, 3, 2, 2, 2]	[1, 2]	Each appears 3 > 2.67 times
[2, 2, 1, 3]	[2]	2 appears 2 > 1.33 times
[1, 2, 3, 4]	[]	Nobody clears the threshold

(Confirm: return every value appearing strictly more than ⌊n/3⌋ times, in sorted order; a majority is not guaranteed.)

How interviewers phrase it

• "Find all elements that appear more than n/3 times" (LeetCode 229).
• "Can you do it in O(n) time and O(1) space?"
• The general version: more than n/k times, with k − 1 candidates.

Clarifying questions to ask

1. Strictly more than n/3?
2. Is the answer guaranteed to be non-empty?
3. Does the output order matter?
4. Is O(1) extra space required?

Follow-ups to expect

1. "Why at most two answers?"
2. "How do two counters work?"
3. "Why is the verification pass necessary?"
4. "How does it generalise to n/k?"
5. "Complexity?"

Related questions

• Majority Element-I Easy
• Count subarrays with given xor K Hard
• Reverse Pairs Hard
• Book Allocation Problem Hard
• Split array - largest sum Hard
• Minimize Max Distance to Gas Station Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in