# Finding the majority element of a stream

DevFeed: [Finding the majority element of a stream](<https://devfeed.tech/articles/finding-the-majority-element-of-a-stream-40379.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2015/03/09/finding-the-majority-element-of-a-stream/>)

Published: 2015-03-09T09:00:11Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [Python](<https://devfeed.tech/topics/python.md>), [data](<https://devfeed.tech/topics/data.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [counter](<https://devfeed.tech/tags/counter.md>), [data-mining](<https://devfeed.tech/tags/data-mining.md>), [frequency-moments](<https://devfeed.tech/tags/frequency-moments.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [pair](<https://devfeed.tech/tags/pair.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [space](<https://devfeed.tech/tags/space.md>), [stream](<https://devfeed.tech/tags/stream.md>), [streaming-algorithms](<https://devfeed.tech/tags/streaming-algorithms.md>), [streaming-data](<https://devfeed.tech/tags/streaming-data.md>), [sublinear-space](<https://devfeed.tech/tags/sublinear-space.md>)

## AI overview

This article presents a Python algorithm for finding the value that occurs more than half the time in a massive data stream. It explains the pairing-based correctness argument, single-pass operation, O(log(n) + log(m)) space usage, the necessity of the majority guarantee, and a k-counter generalization for detecting frequent items.

## Source excerpt

Problem: Given a massive data stream of $ n$ values in $ \{ 1, 2, \dots, m \}$ and the guarantee that one value occurs more than $ n/2$ times in the stream, determine exactly which value does so. Solution: (in Python) def majority(stream): held = next(stream) counter = 1 for item in stream: if item == held: counter += 1 elif counter == 0: held = item counter = 1 else: counter -= 1 return held Discussion: Let's prove correctness.