Streaming Majority Element in O(1) Space
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.