# The Crowd Pleaser

> One value shows up more than all others combined.

Canonical URL: <https://datadriven.io/problems/the_crowd_pleaser>

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given a list of integers, return the element appearing strictly more than n//2 times (where n is the list length). You may assume such an element always exists.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests whether a candidate knows **Boyer-Moore majority vote**, an O(n) time, O(1) space algorithm for finding a majority element. It distinguishes candidates who rely on sorting or hash maps from those who know optimal algorithms.

> **Trick to Solving**
>
> Use Boyer-Moore voting: maintain a candidate and a count. When count drops to 0, switch candidates. The majority element survives because it appears more than n/2 times and cannot be fully cancelled out.

---

### Break down the requirements

#### Step 1: Initialize candidate and count

Start with no candidate and count 0.

#### Step 2: Scan through the list updating the vote

If count is 0, adopt the current element as candidate. If it matches, increment; otherwise decrement.

#### Step 3: Return the surviving candidate

Since the problem guarantees a majority exists, the final candidate is the answer.

---

### The solution

**Boyer-Moore majority vote**

```python
def majority_element(nums: list) -> int:
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
    return candidate
```

> **Time and Space Complexity**
>
> **Time:** O(n) single pass through the list.
> 
> **Space:** O(1). Only two variables regardless of input size.

> **Interviewers Watch For**
>
> Whether you jump to a hash map (O(n) space) or sorting (O(n log n) time) first. Boyer-Moore is the gold-standard answer and shows depth of algorithm knowledge.

> **Common Pitfall**
>
> Assuming the majority element is the most frequent. Majority means strictly more than n/2, not just the mode. Without the guarantee, a verification pass would be needed.

---

## Common follow-up questions

- What if no majority is guaranteed? _(Tests adding a second pass to verify the candidate actually exceeds n/2 occurrences.)_
- Can you find two elements that each appear more than n/3 times? _(Tests the generalized Boyer-Moore with two candidates.)_
- Why does this algorithm work? _(Tests ability to explain the cancellation proof intuitively.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_crowd_pleaser)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.