L52 · Design II — Streams & Time

Series: LeetCode — From Basics to Interview-Ready · Session 52 / 65 · Phase 3 · Advanced & specialised

Why this session exists

The two-heap median is a beautiful reusable idea and it deserves a session on its own merits. The problem — maintain the median of a stream where elements keep arriving — looks like it needs a sorted structure, and sorted insertion is O(n) per element. Two heaps get it to O(log n) with a construction that takes thirty seconds to explain once you see it.

The construction: split the data at the median into a lower half and an upper half. Keep the lower half in a max-heap so its largest element — the one nearest the median — is at the root. Keep the upper half in a min-heap so its smallest is at the root. The median is now always one or both of the two roots, available in O(1). Insertion is a push, a cross-push to maintain the split, and a rebalance if the sizes drift apart.

The idea reappears. Sliding window median is the same structure with lazy deletion bolted on. IPO and various scheduling problems use two heaps for the same reason: you want cheap access to the boundary between two groups that are each internally ordered.

The other two problems today are different lessons. Time Based Key-Value Store is about recognising that "the value as of time T" is a predecessor search on a sorted array, which is binary search — and that append-only writes with increasing timestamps keep the array sorted for free, so you never sort. Design Twitter is about resisting the urge to precompute: merging k sorted feeds on demand with a heap is simpler and usually better than maintaining a materialised timeline per user.

All three share a theme: data arrives over time, and the structure you choose is the one whose invariant survives that arrival cheaply.

Blank-file warm-up

Five minutes, empty file, no notes. Write the two-heap median structure:

1. Both heaps declared, with a comment on how the max-heap is faked using negation.
2. The addNum sequence: push, cross-push, rebalance.
3. findMedian for both odd and even total counts.

The negation is worth stating explicitly because Python has no max-heap. heappush(low, -x) and the root is -low[0]. Getting a sign wrong here produces a structure that silently maintains the wrong halves.

Pattern anatomy

The shape that summons this pattern: elements arrive one at a time, and after each arrival you must answer a query about the whole collection so far. Sorting the collection per query is O(n log n) each time; the design question is what incremental structure keeps the answer cheap.

The invariant for the two-heap median is three clauses, and all three must hold after every operation:

1. Every element in low is less than or equal to every element in high.
2. len(low) equals len(high) or len(low) == len(high) + 1.
3. low is a max-heap and high is a min-heap.

Clause 1 is what makes the roots the median candidates. Clause 2 fixes which side holds the extra element when the count is odd, so findMedian needs no case analysis beyond parity.

import heapq
 
class MedianFinder:
    def __init__(self):
        self.low = []      # max-heap via negation: the smaller half
        self.high = []     # min-heap: the larger half
 
    def addNum(self, num: int) -> None:
        heapq.heappush(self.low, -num)                       # always land in low
        heapq.heappush(self.high, -heapq.heappop(self.low))  # cross-push the max
        if len(self.high) > len(self.low):                   # rebalance
            heapq.heappush(self.low, -heapq.heappop(self.high))
 
    def findMedian(self) -> float:
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2.0

The three-line addNum deserves attention because it looks like it does unnecessary work. Push unconditionally into low, then immediately move low's maximum into high. That guarantees clause 1 without any comparison: whatever ends up in high is at least as large as everything remaining in low, because it was the maximum of low after the insertion. Then one size check restores clause 2.

The alternative — compare the incoming number against the roots and decide which heap to push into — is also correct and is arguably more intuitive, but it needs two or three branches and each branch needs its own rebalance. The unconditional version is three lines with one branch. Write the three-line version.

Time Based KV is a different structure entirely:

import bisect
from collections import defaultdict
 
class TimeMap:
    def __init__(self):
        self.store = defaultdict(list)     # key -> list of (timestamp, value)
 
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))   # timestamps arrive increasing
 
    def get(self, key: str, timestamp: int) -> str:
        arr = self.store.get(key)
        if not arr:
            return ""
        # find the rightmost entry with timestamp <= the query
        i = bisect.bisect_right(arr, (timestamp, chr(0x10FFFF)))
        return arr[i - 1][1] if i else ""

The sentinel chr(0x10FFFF) in the search tuple is there so that an exact timestamp match sorts after every real value at that timestamp, making bisect_right land just past it. In an interview you would more likely write the binary search by hand on timestamps only, which avoids the tuple-comparison subtlety entirely and is clearer.

The cue

You are looking at a streaming-design problem when the statement contains these tells:

1. "Data stream", "as they arrive", "online" — elements come one at a time and you cannot see the future or re-read the past cheaply.
2. A query about a positional statistic — median, k-th largest, top-k. Positional statistics under insertion is the two-heap or single-heap signature.
3. A timestamp parameter on both the write and the read. That is versioned storage, and "the value at or before time T" is a predecessor query, which is binary search.
4. "Design" plus multiple entities with a many-to-many relation — users, follows, posts. Usually a merge or fan-out question.
5. Explicit per-operation complexity requirements like "get in O(1), add in O(log n)". The asymmetry tells you which operation to make cheap at the other's expense.

Tell 5 is worth internalising as a general design habit. When a spec makes one operation cheaper than another, it is telling you where to put the work. Cheap reads and expensive writes means precompute; the reverse means compute lazily.

Guided solve

Find Median from Data Stream — implement addNum(num) and findMedian(). Numbers arrive one at a time.

Start by rejecting the obvious approaches out loud, with reasons.

Keep an unsorted list, sort on each query. addNum is O(1) but findMedian is O(n log n). If queries are frequent this is hopeless.

Keep a sorted list, insert in position. findMedian is O(1) but insertion into an array is O(n) because of the shifting, even though finding the position is O(log n) by binary search. Note the subtlety here: bisect.insort is often mistaken for O(log n), but the search is logarithmic and the insertion is linear.

Use a balanced BST with subtree sizes. O(log n) for both, and genuinely correct — this is what a language with an order-statistic tree would do. Python has no such structure in the standard library, and writing one in an interview is not a good use of time.

Now the two-heap insight. You do not need the collection sorted. You need one or two specific elements: the middle one, or the middle two. So maintain just enough order to know what those are.

Split the data at the median. Everything at or below it goes in low; everything above goes in high. If low is a max-heap, its root is the largest of the smaller half — a median candidate. If high is a min-heap, its root is the smallest of the larger half — the other candidate. When the total count is odd, put the extra element in low by convention, and the median is low's root. When it is even, the median is the average of the two roots.

That is the design. Now the operations.

Insertion. The new number belongs in low if it is at most low's root, and in high otherwise. The three-line trick sidesteps that comparison: push into low unconditionally, then pop low's maximum and push it into high. If the new number was large, it is the thing that just moved to high — correct. If it was small, something else moved instead and the new number stays in low — also correct. The invariant holds either way.

Rebalancing. After the cross-push, high may have one more element than low, violating the convention. Move high's minimum back to low. Sizes now differ by at most one with low never smaller.

Query. If the sizes differ, low has the extra element and its root is the median. If they are equal, average the two roots. Cast to float or use / 2.0, because integer division on an even count is a real and easy bug.

Trace: add 1. low = [-1], cross-push makes low = [], high = [1], rebalance moves it back so low = [-1], high = []. Median is 1. Add 2. Push gives low = [-2, -1], cross-push moves 2 to high, so low = [-1], high = [2]. Sizes equal, median is 1.5. Add 3. Push gives low = [-3, -1], cross-push moves 3, so low = [-1], high = [2, 3]; rebalance moves 2 back, giving low = [-2, -1], high = [3]. Median is 2. Correct throughout.

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• Find Median from Data Stream — the full two-heap structure. Target six minutes; it is short once the invariant is clear.
• Time Based Key-Value Store — write the binary search by hand rather than using bisect on tuples. Decide before you code whether you want the rightmost entry with timestamp at most the query, and which of lo or hi holds it when the loop ends.
• Design Twitter — merge on read with a heap. Cap each user's stored posts at ten if you like; think about whether that cap is safe.

Common failure modes

Sign errors in the negated max-heap. Push -num, read -low[0], and when moving between heaps negate exactly once. A single missed negation gives a structure that maintains the wrong halves and produces medians that look almost right.

Rebalancing in only one direction. With the unconditional-push formulation only high can become oversized, so one check suffices. If you write the comparison-based insertion instead, both directions can drift and you need two checks. Match your rebalance to your insertion.

Integer division on the even case. (a + b) // 2 on the roots gives 1 instead of 1.5. Use / 2.0, or make one operand a float.

Sorting the timestamp list in TimeMap. If timestamps are guaranteed strictly increasing across calls — and the problem states this — appends keep the list sorted for free. Sorting on every set turns O(1) writes into O(n log n) and is pure waste.

Binary search returning the wrong side in TimeMap. You want the rightmost entry with timestamp at most the query. Off by one gives the next entry, which is a value from the future. Test with an exact timestamp match and with a query before every stored timestamp.

Fan-out on write in Design Twitter. Pushing to every follower's timeline on each post is O(followers) per post and is exactly the wrong trade for this problem's operation mix.

Complexity

MedianFinder.addNum: O(log n). One push, one pop, one push, and at most one more pop-push pair for the rebalance — a bounded number of heap operations, each logarithmic in the current size.

MedianFinder.findMedian: O(1). Reading one or two heap roots and doing arithmetic. No traversal.

Space: O(n) — every element is stored exactly once across the two heaps.

TimeMap.set: O(1) amortised — a single list append, valid because timestamps arrive in increasing order and the list therefore stays sorted with no work. TimeMap.get: O(log n) in the number of entries for that key, by binary search. Space O(total writes), since nothing is ever overwritten — this is versioned, append-only storage.

Design Twitter with merge-on-read: postTweet is O(1), follow and unfollow are O(1) with a set. getNewsFeed is O(k log k) where k is the number of followees, if you seed a heap with each followee's most recent tweet and pop ten times — the log factor is over the number of feeds, not the number of tweets. Fan-out on write inverts this: O(followers) per post and O(1) per feed read.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

The two-heap structure is worth a shorter interval than the ladder suggests, because the negation details decay quickly even when the idea does not. Re-derive the invariants each time rather than recalling the code.