Track the Running Twice-Median of a Live Price Feed

Hard30–35 min

Topics

HeapTwo HeapsDesignData Stream

Companies

AmazonGoogleMicrosoftBloomberg

A trading desk receives a live feed of prices. You are given a log of events: record adds a price to the feed, and query asks for the median of every price recorded so far. Report each median doubled (for an odd count that is twice the middle price; for an even count it is the sum of the two middle prices) so the answers are always integers, and return them in order.

Re-sorting the entire history on every query gets slower as the feed grows. Keeping the smaller half of the prices in a max-heap and the larger half in a min-heap puts the median right at the two roots, so a query is instant and each new price only costs a heap insertion.

Test Case 1:

Input:ops = ["record","record","query","record","query","record","query"], values = [8,2,0,6,0,10,0]

Output:[10, 12, 14]

Explanation:Prices {2, 8} have median 5 → doubled 10. Adding 6 gives {2, 6, 8}, median 6 → 12. Adding 10 gives {2, 6, 8, 10}, median (6+8)/2 = 7 → 14.

Test Case 2:

Input:ops = ["record","query"], values = [7,0]

Output:[14]

Explanation:A single price is its own median; doubled, 14.

Test Case 3:

Input:ops = ["record","record","query"], values = [-5,5,0]

Output:[0]

Explanation:The two middle prices are -5 and 5; their sum, 0, is the doubled median.

Constraints

◆1 ≤ ops.length ≤ 100, and values.length equals ops.length
◆Each op is "record" (add values[i] to the feed) or "query" (report the current median, doubled)
◆-1000 ≤ values[i] ≤ 1000 for every "record"; the values entry of a "query" is ignored
◆At least one "record" appears before every "query"
◆The median of an even number of prices is the average of the two middle prices; report it doubled so the answer is always an integer

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Re-Sort Every Recorded Price on Each Query

Brute

Store every recorded price in a plain list. When a query arrives, copy the list, sort the copy, and read the middle: for n prices the doubled median is sorted[(n-1)/2] + sorted[n/2], which works for both odd and even n. It is easy to get right, but every single query sorts everything recorded so far from scratch — long feeds with frequent queries make this very slow.

TimeO(q · n log n)

SpaceO(n)

Java

Try it out

class Solution {
    public List<Integer> runningTwiceMedian(String[] ops, int[] values) {
        List<Integer> seen = new ArrayList<>();
        List<Integer> answers = new ArrayList<>();
        for (int i = 0; i < ops.length; i++) {
            if (ops[i].equals("record")) {
                seen.add(values[i]);
            } else {
                List<Integer> sorted = new ArrayList<>(seen);
                Collections.sort(sorted);
                int n = sorted.size();
                answers.add(sorted.get((n - 1) / 2) + sorted.get(n / 2));
            }
        }
        return answers;
    }
}

Optimal — Two Heaps Split Around the Median

Optimal

Split the recorded prices into two halves and keep each half in a heap: a max-heap "low" holding the smaller half and a min-heap "high" holding the larger half. The invariant is that every price in low is ≤ every price in high, and low is either the same size as high or exactly one larger. Then the median sits at the roots: if low is bigger it is low's root (doubled), otherwise it is the average of the two roots (their sum, doubled). A new price goes into low if it is ≤ low's root, otherwise into high; if that leaves the sizes unbalanced, the root of the too-large heap is moved across. Every record costs O(log n) and every query costs O(1). (In the C solution the max-heap is a min-heap of negated values.)

TimeO(n log n)