Streaming Majority Element in O(1) Space

Reported in interviews at D. E. Shaw

Problem statement

You are given a stream of $n$ integers, one at a time. You know that some element appears strictly more than $n/2$ times, but you do not know which one.

Design a streaming algorithm that identifies this majority element using $O(1)$ space and $O(n)$ time (a single pass through the stream).

Constraints:

  • $1 \leq n \leq 10^7$
  • Exactly one element appears more than $\lfloor n/2 \rfloor$ times
  • You may only make a single pass over the data (streaming model)
  • $O(1)$ auxiliary space (you cannot store the array)

Example 1:

  • Input: [3, 3, 4, 2, 3, 3, 5, 3]
  • Output: 3
  • Explanation: 3 appears 5 times out of 8 elements ($5 > 8/2$), so 3 is the majority element.

Example 2:

  • Input: [1, 2, 1, 1, 2, 1]
  • Output: 1
  • Explanation: 1 appears 4 times out of 6 elements ($4 > 6/2$), so 1 is the majority element.

Example 3:

  • Input: [7]
  • Output: 7
  • Explanation: The single element is trivially the majority.
Show hint

Which elements could you safely throw away in pairs without ever losing the value you are looking for?

Relevant roles: ML Engineer, Data Scientist, MLOps Engineer and Applied Scientist.

Related free problems