# Dominant Element

> Majority element. Appears more than half the time.

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

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given a list of integers where one element appears strictly more than half the time, return that element. You may assume such an element exists.

## Worked solution and explanation

### Why this problem exists in real interviews

Finding the majority element tests knowledge of **Boyer-Moore voting algorithm**, the classic O(n) time, O(1) space solution. It separates candidates who know algorithmic patterns from those who default to brute-force counting.

> **Trick to Solving**
>
> Boyer-Moore voting: maintain a candidate and a count. When count drops to zero, switch the candidate. The dominant element survives because it appears more than half the time, so it can never be fully canceled out by other elements.

---

### Break down the requirements

#### Step 1: Track a candidate and a counter

Start with the first element as the candidate and count 1.

#### Step 2: Iterate and adjust the count

If the current element matches the candidate, increment count. Otherwise, decrement. When count reaches 0, adopt the current element as the new candidate.

#### Step 3: Return the surviving candidate

The element that survives the voting process is guaranteed to be the dominant element when one exists.

---

### The solution

**Boyer-Moore majority vote in a single pass**

```python
def find_dominant(readings):
    if not readings:
        return None
    candidate = readings[0]
    count = 1
    for i in range(1, len(readings)):
        if count == 0:
            candidate = readings[i]
            count = 1
        elif readings[i] == candidate:
            count += 1
        else:
            count -= 1
    return candidate
```

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

> **Interviewers Watch For**
>
> Whether you know Boyer-Moore voting. A Counter-based approach works but uses O(n) space. Boyer-Moore is the canonical optimal solution for this problem.

> **Common Pitfall**
>
> Not verifying the candidate with a second pass when the problem does not guarantee a dominant element exists. Here the prompt guarantees one exists, but in general you should verify.

---

## Common follow-up questions

- What if no dominant element is guaranteed to exist? _(Tests adding a verification pass that counts the candidate's actual frequency.)_
- Can you find elements appearing more than n/3 times? _(Tests extending Boyer-Moore to track two candidates simultaneously.)_
- How would this work in a distributed system with partitioned data? _(Tests combining partial results: merge candidate/count pairs from each partition.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/dominant_element)
- [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.