Streaming data structures

38 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Numbers arrive one at a time: 2, 3, 5. Someone asks for the first number that has appeared only once: 2. Then 5 arrives again, then 2 again, then 1. Now the first unique number is 3. By hand you keep the whole list and, for each question, read it from the start, counting each value, until you find one that appears once. That is fine for six numbers. For a stream of ten million numbers that never ends, you cannot keep rereading the list, and you may not be able to keep the list at all.

Streaming problems share this shape: items arrive forever, a question can come at any time, and the answer must come quickly. The by-hand method stores everything and recomputes from scratch. The streaming method stores only a summary and updates it a little per item.

Build the structure, one piece at a time

Piece one: a count per value, in a hash map. After 2, 3, 5 the counts are {2: 1, 3: 1, 5: 1}. This answers "has this value appeared once?" instantly, but not "which unique value came first".

Piece two: a queue of candidates in arrival order. Every new value is appended, so the queue remembers the order: [2, 3, 5]. The first unique number is the first queue entry whose count is 1.

Piece three: lazy cleaning. When 5 arrives again, its count becomes 2. We do not search the queue to remove 5; that would be slow. We leave it there and only look at the front when a question is asked. If the front's count is above 1, pop it and look again, until the front is unique:

Other streaming questions use other summaries of the same spirit: a moving average keeps a queue of the last k values and their running total; the k-th largest so far keeps a heap of the k largest; the median keeps two heaps, one for each half.

Why it is correct

The invariant is that the summary answers the question exactly as the whole history would. For first-unique that means: the counts are the true counts of every value seen, and every value that is currently unique is in the queue, in arrival order, possibly behind some stale entries. Adding a value keeps both facts: the count is incremented, and a brand new value is appended to the end, so it sits after every earlier value. A value that becomes repeated stays in the queue but its count says it is stale. When a question is asked, popping stale fronts cannot remove a unique value, because a stale entry is one whose count exceeds 1. So the first front with count 1 is the earliest-arrived unique value, which is the right answer, and if the queue empties there is none.

Why it is fast

Each arrival does one hash update and at most one append, O(1). Each value is pushed into the queue at most once (only on its first arrival) and popped at most once, so all the popping over the whole stream costs at most the number of distinct values. A single question may pop several stale entries, but that cost is paid once per entry, never again. Averaged over all calls, every operation is amortised O(1). The memory is one count per distinct value plus the queue, which is at most one entry per distinct value, so O(d) for d distinct values, and never a copy of the stream.

total pops ≤ total pushes ≤ d

How to recognise it in an interview

Cues: "stream", "data arrives one at a time", "design a class with add and query", "cannot store all the data", "moving", "so far", "last k". Say: "I will keep a small summary that the queries can be answered from and update it per item; stale entries can be cleaned lazily when they reach the front".

Find Median from Data Stream keeps a max-heap of the lower half and a min-heap of the upper half, balanced in size, so the median is a root. Kth Largest Element in a Stream keeps a min-heap of size k whose root is the answer. Moving Average from Data Stream keeps a queue of the last k numbers and their sum, subtracting the one that leaves.

02The idea in one line

Process one item at a time with O(1) or O(log n) state; never store the whole stream.

Reach for it when: Moving average, kth largest in a stream, first unique in a stream, median.

Cost: O(log n) per item.

03The walk-through, step by step

The video works one example: First Unique Number stream: 2,3,5 ; add 5 ; add 2. These are its captions in order, so you can follow without the video or check a step you missed.

1. Never store the whole stream: a queue of candidates plus a count map
2. add(2): count becomes 1, push to the queue
3. add(3): count becomes 1, push to the queue
4. add(5): count becomes 1, push to the queue
5. showFirstUnique() → 2
6. add(5): count 2, no longer unique; lazily stays queued
7. add(2): count 2, no longer unique; lazily stays queued
8. add(1): new value, push it
9. front 2 has count 2 > 1: stale, pop it
10. showFirstUnique() → 3
11. Each value is pushed once and popped once: amortised O(1) per call

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Design: Hash map + doubly linked list (LRU), Hash map + array for O(1) random, Time-versioned map, Lazy iterators, Ordered intervals (range module).