How do you find the majority element? | Interview Question

Q: How do you find the majority element?

**Target Audience:** Beginners preparing for coding interviews — you know Python lists and loops; nothing else assumed. **Difficulty:** Easy **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every output shown was produced by running the code with `python3` (3.13); nothing is typed in by hand. ## 1. Why This Even Matters — A Story First A crowd of supporters from different football clubs is in a hall. You are told that **more than half** of the people support one club, and you need to find out which — but you have no paper, and you can only remember one club name and one number at a time. Here is a trick. Ask people to walk out of the hall in pairs, and every pair must be two supporters of **different** clubs. Keep going until no such pair can be formed. The people left in the hall all support the same club — and it has to be the majority

The problem

Question presented to candidate: "Given a list of integers, return the majority element — the value that appears more than n/2 times. First assume one always exists, then tell me what changes if it might not. Please code it in Python and aim for O(1) extra space."

What a strong answer should cover:

The definition: more than ⌊n/2⌋ occurrences, so at most one majority can exist; exactly half is not a majority.
The simple answers: counting with a dict/Counter (O(n) time, O(n) space) and sorting then taking index n // 2 (O(n log n)).
Boyer-Moore voting: one candidate and one counter, O(n) time and O(1) space, with the cancelling-pairs argument for why it is correct.
The verification pass when a majority is not guaranteed ([1, 2, 3] yields candidate 3).
Python specifics: Counter(nums).most_common(1), nums.count(candidate) for the verify pass, // for floor division, and that statistics.mode returns the most common value, which is not necessarily a majority.

Clarifying questions expected:

Is a majority guaranteed? What should be returned if there is none?

Code / implementation expected: Yes — a Boyer-Moore majority(nums) in Python with an optional verify pass, run on inputs with and without a majority.

arrays
boyer-moore

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you know Python lists and loops; nothing else assumed. Difficulty: Easy Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every output shown was produced by running the code with python3 (3.13); nothing is typed in by hand.

1. Why This Even Matters — A Story First

A crowd of supporters from different football clubs is in a hall. You are told that more than half of the people support one club, and you need to find out which — but you have no paper, and you can only remember one club name and one number at a time.

Here is a trick. Ask people to walk out of the hall in pairs, and every pair must be two supporters of different clubs. Keep going until no such pair

The solution is hidden so you can try first

12 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonBoyer-Moore voting with a verify pass on seven inputs

Practice

PythonTrace of the vote, the no-majority trap, and vote vs count vs sort

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.