cppintermediate15 minutes

Build a Function to Compute Running Median from a Stream of Integers

Write a C++ function that accepts a vector of integers representing a stream of numbers and returns a vector containing the running median after each new number is added.

Challenge prompt

Create a function named `runningMedian` that takes a const reference to a vector of integers. For each new integer added from the stream, the function should compute the median of all numbers seen so far and append it to a result vector. Return the vector of running medians. The median of a list is the middle number after sorting; if the size is even, the median is the average of the two middle numbers (as a double).

Guidance

• Use appropriate data structures to efficiently maintain the elements seen so far in sorted order.
• Consider how to find the median quickly after each insertion without sorting the entire list every time.
• Make sure to handle both odd- and even-sized sets correctly when computing the median.
• Return the medians as vector<double> to handle fractional medians.

Hints

• Use two heaps (priority queues) — a max heap for the lower half, a min heap for the upper half — to track medians efficiently.
• Balance the heaps so they differ in size by no more than one element.
• The median can be derived from the top elements of the two heaps depending on their sizes.

Starter code

#include <vector>
#include <queue>

std::vector<double> runningMedian(const std::vector<int>& stream) {
    // Implement your solution here
}

Expected output

For input: {2, 1, 5, 7, 2, 0, 5} Output: {2.0, 1.5, 2.0, 3.5, 2.0, 2.0, 2.0}

Core concepts

heapspriority_queuemedian calculationstream processing

Challenge a Friend

Send this duel to someone else and see if they can solve it.