DSA interview question

Majority Element (More Than n/2 Times)

Easy · Algorithms · Topics: array, counting, boyer moore

The problem

An election is decided by a single ballot box, and the rules say a candidate wins outright if they get more than half of all votes. The counting machine has very little memory: it can't keep a tally for every candidate. Boyer–Moore voting finds the majority in one pass using just a candidate and a counter. It's a pairing argument: every vote for someone else cancels one vote for the majority, and a majority can't be cancelled out completely.

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

Function signature

int majorityElement(const vector<int>& nums);  // the element appearing more than n/2 times (guaranteed to exist)

Test cases

Input `nums`	Output	Explanation
`[3, 2, 3]`	3	2 of 3 votes
`[2, 2, 1, 1, 1, 2, 2]`	2	4 of 7 votes
`[1]`	1
`[6, 5, 5]`	5
`[7, 7, 7, 3, 3]`	7

(Confirm: a majority element always exists; without that guarantee, a second pass must verify the candidate.)

How interviewers phrase it

"Find the majority element, which appears more than n/2 times" (LeetCode 169).
"Can you do it in O(n) time and O(1) space?"
Follow-up: "Find all elements appearing more than n/3 times" (S.No 91).

Clarifying questions to ask

Is a majority guaranteed to exist?
Is O(1) extra space required?
More than n/2, or at least n/2?

Follow-ups to expect

"Why does the voting algorithm work?"
"What if a majority isn't guaranteed?"
"Other approaches?"
"How does it extend to n/3?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview