Find the value that fills more than half the list

Arrays, strings and hash maps Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
cand, n = 0, 0
for v in [2, 2, 1, 1, 2]:
    if n == 0:
        cand = v
    n += 1 if v == cand else -1
print(cand, n)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 2 1

Right: 2 leads, 1 and 1 cancel it to zero, and the last 2 restarts it at 1.

The counter ends as a leftover margin, not a tally, which is why a confirmation pass is needed without the guarantee.

Why not the others?
  • B 1 0. After the two 1s the counter is 0, but the final 2 becomes the candidate.
  • C 2 3. The counter is a margin, not the number of 2s.

30-second answer

Use a pair-cancelling vote: keep a candidate and a counter. A matching value adds one, a different value subtracts one, and at zero the next value becomes the candidate. Each cancellation removes one vote for the winner at most together with one other vote, so the winner survives. O(n) time, O(1) space.

Practise saying it · 45 s. No recording, just a timer

Explain the cancelling vote and when you must confirm the result.

Say your answer out loud, then check which of these points you covered:

  • Candidate and counter
  • Why the winner survives
  • Second pass without the guarantee

Deep dive

Think of it as pairing off different values: since the winner has more than half, it cannot be fully paired away.

The guarantee matters. Without it, run a second pass to count the candidate and confirm it really has more than half.

A Counter solves it in O(n) time too, but needs O(n) memory, which the question rules out.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def over_half(votes: list[int]) -> int:
    candidate, lead = 0, 0
    for v in votes:
        if lead == 0:
            candidate = v
        lead += 1 if v == candidate else -1
    return candidate

Common mistakes

  • Skipping the confirmation pass when the guarantee is not given.
  • Resetting the candidate on every mismatch instead of only when the counter hits zero.

Senior take & follow-ups

Explain the cancelling argument, then offer the second pass for when the guarantee is missing. That shows you read the constraint.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if you need every value above a third?

    Show hint

    Keep two candidates and two counters, then confirm both in a second pass.

  2. Can sorting help?

    Show hint

    After sorting, the middle element is the answer, at O(n log n).

What each operation costs: Arrays · Dynamic Arrays · Hash Table · Hash Functions

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.