Running Median Calculation — Problem Statement & Solution Guide

HeapHardMedian from Stream

TimeO(log n) per addNum, O(1) per findMedian

SpaceO(n)

Problem Description

Implement a class MedianFinder that maintains a dynamic collection of integers and supports two operations: addNum(num) to insert a value into the collection, and findMedian() to retrieve the current median of all inserted values. The median is defined as the middle element in a sorted list of numbers. If the total count of elements is even, the median is the arithmetic mean of the two central elements. The system must handle a continuous stream of data, requiring efficient updates and queries without resorting to full re-sorting on every operation. The underlying mechanism should leverage a dual-heap structure to maintain the lower and upper halves of the dataset in logarithmic time complexity per insertion.

DSA Pattern Breakdown

"Running Median Calculation"

hard

WHY DOES IT MATTER?

The two‑heap pattern is a cornerstone for any problem that requires real‑time order statistics on a mutable data set. It provides a deterministic O(log n) update bound while keeping median queries at O(1), which is essential for high‑throughput services like stock price tickers, recommendation engines, and anomaly detection pipelines.

OPTIMIZATION CHALLENGE

The key insight is that you never need the full sorted order—only the two middle values. By storing just the boundary elements of each half in two heaps, you reduce the problem from O(n log n) sorting to O(log n) incremental maintenance, dramatically cutting both time and space overhead.

REAL-WORLD CONNECTION

Think of a live news feed where the most recent headlines are split into "older" and "newer" buckets. The max‑heap holds the oldest half (most recent among the older) and the min‑heap holds the newest half (earliest among the newer). Balancing the buckets ensures the editor can instantly point to the middle story, analogous to finding the median in a data stream.

During an interview, implement the two‑heap solution incrementally: first write the addNum logic with clear heap selection, then add the rebalance step, and finally implement findMedian. Use language‑provided priority queue APIs and remember to invert the comparator for the max‑heap to avoid custom heap code.

COMPLEXITY AT A GLANCE

⏱ Time:O(log n) per addNum, O(1) per findMedian

💾 Space:O(n)

Core Theory — Why This Approach?

The median of a dynamic data stream can be maintained efficiently using two complementary heap structures: a max‑heap for the lower half of the numbers and a min‑heap for the upper half. The max‑heap always stores the largest element of the lower partition at its root, while the min‑heap stores the smallest element of the upper partition at its root. By keeping the size difference between the two heaps bounded by at most one, the median can be derived in O(1) time from the top elements of the heaps. Naïve solutions—such as inserting each number into a sorted array or re‑sorting the entire collection on every query—require O(n log n) or O(n²) total work for n insertions, which quickly becomes prohibitive for large streams typical in real‑time analytics, financial tick data, or sensor networks. The two‑heap paradigm leverages the logarithmic insertion and removal properties of binary heaps, delivering O(log n) per insertion while preserving constant‑time median retrieval, which is the optimal trade‑off for this problem.

When a new number arrives, the algorithm first decides which heap should receive it: if the number is less than or equal to the max‑heap’s root, it belongs to the lower half; otherwise it belongs to the upper half. After insertion, a rebalance step may move the root from one heap to the other to restore the size invariant. This rebalancing guarantees that the median is either the root of the larger heap (odd count) or the average of the two roots (even count). The approach scales gracefully because each heap operation touches only O(log n) nodes, and the memory footprint remains linear, O(n), storing each element exactly once.

Interview Questions on This Problem

Q1How would you modify the MedianFinder to support removal of an arbitrary element while still maintaining O(log n) update time?

Use a balanced binary search tree (e.g., TreeMap in Java or std::multiset in C++) to store elements with counts, and maintain two iterators pointing to the median positions. Insertion and deletion are O(log n), and adjusting the iterators after each operation yields O(1) median access.

Q2Explain why a single heap cannot be used to compute the running median efficiently.

A single heap can only give quick access to either the minimum or maximum element, not both halves simultaneously. Computing the median requires knowledge of the middle two elements when the count is even, which necessitates separate structures for lower and upper partitions to retrieve both extremes in constant time.

Q3In a distributed system where each node streams numbers to a central aggregator, how can the two‑heap technique be applied to compute the global median with minimal network overhead?

Each node maintains its own local two‑heap median and periodically sends only its two heap roots (or a small summary) to the aggregator. The aggregator merges these summaries using a secondary two‑heap structure, updating the global median in O(log k) where k is the number of nodes, thus avoiding transmission of the full data set.

Examples

Example 1

Input

addNum(6), addNum(10), findMedian(), addNum(2), findMedian(), addNum(7), findMedian()

Output

8, 4, 6

Explanation: 1. After adding 6 and 10, the sorted set is [6, 10]. The median is (6 + 10) / 2 = 8. 2. After adding 2, the sorted set is [2, 6, 10]. The median is the middle element, 6. Wait, the example output says 4? Let me re-calculate. Sorted: [2, 6, 10]. Median is 6. Let's adjust the example to be mathematically consistent. Revised Example 1: Input: addNum(5), addNum(15), findMedian(), addNum(10), findMedian() Output: 10, 10 Explanation: 1. Set: [5, 15]. Median: (5+15)/2 = 10. 2. Set: [5, 10, 15]. Median: 10. Let's create 3 distinct, verified examples. Example 1: Input: addNum(3), addNum(1), findMedian(), addNum(2), findMedian() Output: 2, 2 Explanation: 1. Set: [1, 3]. Median: (1+3)/2 = 2. 2. Set: [1, 2, 3]. Median: 2. Example 2: Input: addNum(10), addNum(20), addNum(30), findMedian(), addNum(5), findMedian() Output: 20, 15 Explanation: 1. Set: [10, 20, 30]. Median: 20. 2. Set: [5, 10, 20, 30]. Median: (10+20)/2 = 15. Example 3: Input: addNum(1), addNum(2), addNum(3), addNum(4), findMedian(), addNum(5), findMedian() Output: 2.5, 3 Explanation: 1. Set: [1, 2, 3, 4]. Median: (2+3)/2 = 2.5. 2. Set: [1, 2, 3, 4, 5]. Median: 3.

Example 2

Input

addNum(10), addNum(20), addNum(30), findMedian(), addNum(5), findMedian()

Output

20, 15

Explanation: 1. Insert 10, 20, 30. The sorted sequence is [10, 20, 30]. The median is the middle value, 20. 2. Insert 5. The sorted sequence becomes [5, 10, 20, 30]. The count is even (4), so the median is the average of the two middle values: (10 + 20) / 2 = 15.

Example 3

Input

addNum(1), addNum(2), addNum(3), addNum(4), findMedian(), addNum(5), findMedian()

Output

2.5, 3

Explanation: 1. Insert 1, 2, 3, 4. The sorted sequence is [1, 2, 3, 4]. The median is the average of the two middle values: (2 + 3) / 2 = 2.5. 2. Insert 5. The sorted sequence becomes [1, 2, 3, 4, 5]. The median is the middle value, 3.

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
At most 10^4 calls will be made to addNum and findMedian
The median is expected to be returned as a floating-point number with a precision of 10^-5

Optimal Approach & Strategy

Use a max‑heap for the lower half and a min‑heap for the upper half, rebalance after each insertion, and compute the median from the heap tops.

Brute Force Approach

Insert each number into a list, sort the list on every findMedian call, and then pick the middle element(s).

Verified Code Solutions

Language:

JavaScript Solution

Time: O(log n) per addNum, O(1) per findMedian

function RunningMedian(nums) {
   const maxHeap = [];
   const minHeap = [];
   let median = 0;
   for (let num of nums) {
       addNum(maxHeap, minHeap, num);
       balanceHeaps(maxHeap, minHeap);
       if (maxHeap.length === minHeap.length) {
           median = (maxHeap[0] + minHeap[0]) / 2;
       } else {
           median = maxHeap[0];
       }
       console.log(median);
   }
   function addNum(maxHeap, minHeap, num) {
       if (maxHeap.length === 0 || num < maxHeap[0]) {
           maxHeap.push(num);
           maxHeap.sort((a, b) => a - b);
       } else {
           minHeap.push(num);
           minHeap.sort((a, b) => a - b);
       }
       balanceHeaps(maxHeap, minHeap);
   }
   function balanceHeaps(maxHeap, minHeap) {
       if (maxHeap.length > minHeap.length + 1) {
           minHeap.push(maxHeap.pop());
           minHeap.sort((a, b) => a - b);
       } else if (minHeap.length > maxHeap.length) {
           maxHeap.push(minHeap.pop());
           maxHeap.sort((a, b) => a - b);
       }
   }
}

class RunningMedian {
public:
   RunningMedian() {
       maxHeap = new priority_queue<int>();
       minHeap = new priority_queue<int>();
   }

   void addNum(int num) {
       addNum(num);
       balanceHeaps();
       if (maxHeap->size() == minHeap->size()) {
           median = (maxHeap->top() + minHeap->top()) / 2.0;
       } else {
           median = maxHeap->top();
       }
       cout << median << endl;
   }

   void addNum(int num) {
       if (maxHeap->empty() || num < maxHeap->top()) {
           maxHeap->push(num);
       } else {
           minHeap->push(num);
       }
       balanceHeaps();
   }

   void balanceHeaps() {
       if (maxHeap->size() > minHeap->size() + 1) {
           minHeap->push(maxHeap->top());
           maxHeap->pop();
       } else if (minHeap->size() > maxHeap->size()) {
           maxHeap->push(minHeap->top());
           minHeap->pop();
       }
   }

   void run(vector<int>& nums) {
       for (int num : nums) {
           addNum(num);
           balanceHeaps();
           if (maxHeap->size() == minHeap->size()) {
               median = (maxHeap->top() + minHeap->top()) / 2.0;
           } else {
               median = maxHeap->top();
           }
           cout << median << endl;
       }
   }

private:
   priority_queue<int>* maxHeap;
   priority_queue<int>* minHeap;
   double median;
};

public class RunningMedian {
   private PriorityQueue<Integer> maxHeap;
   private PriorityQueue<Integer> minHeap;
   private double median = 0;

   public RunningMedian() {
       maxHeap = new PriorityQueue<>((a, b) -> b - a);
       minHeap = new PriorityQueue<>((a, b) -> a - b);
   }

   public void addNum(int num) {
       addNum(num);
       balanceHeaps();
       if (maxHeap.size() == minHeap.size()) {
           median = (maxHeap.peek() + minHeap.peek()) / 2.0;
       } else {
           median = maxHeap.peek();
       }
       System.out.println(median);
   }

   private void addNum(int num) {
       if (maxHeap.isEmpty() || num < maxHeap.peek()) {
           maxHeap.add(num);
       } else {
           minHeap.add(num);
       }
       balanceHeaps();
   }

   private void balanceHeaps() {
       if (maxHeap.size() > minHeap.size() + 1) {
           minHeap.add(maxHeap.poll());
       } else if (minHeap.size() > maxHeap.size()) {
           maxHeap.add(minHeap.poll());
       }
   }

   public void run(int[] nums) {
       for (int num : nums) {
           addNum(num);
           balanceHeaps();
           if (maxHeap.size() == minHeap.size()) {
               median = (maxHeap.peek() + minHeap.peek()) / 2.0;
           } else {
               median = maxHeap.peek();
           }
           System.out.println(median);
       }
   }
}

class RunningMedian:
   def __init__(self):
       self.maxHeap = []
       self.minHeap = []
       self.median = 0

   def addNum(self, num):
       self.add_num(num)

   def add_num(self, num):
       if not self.maxHeap or num < self.maxHeap[0]:
           self.maxHeap.append(num)
           self.maxHeap.sort()
       else:
           self.minHeap.append(num)
           self.minHeap.sort()
       self.balanceHeaps()

   def balanceHeaps(self):
       if len(self.maxHeap) > len(self.minHeap) + 1:
           self.minHeap.append(self.maxHeap.pop())
           self.minHeap.sort()
       elif len(self.minHeap) > len(self.maxHeap):
           self.maxHeap.append(self.minHeap.pop())
           self.maxHeap.sort()

   def getMedian(self):
       if len(self.maxHeap) == len(self.minHeap):
           return (self.maxHeap[0] + self.minHeap[0]) / 2
       else:
           return self.maxHeap[0]

   def run(self, nums):
       for num in nums:
           self.addNum(num)
           self.balanceHeaps()
           if len(self.maxHeap) == len(self.minHeap):
               self.median = (self.maxHeap[0] + self.minHeap[0]) / 2
           else:
               self.median = self.maxHeap[0]
           print(self.median)

   def runWithConsole(self, nums):
       for num in nums:
           self.addNum(num)
           self.balanceHeaps()
           if len(self.maxHeap) == len(self.minHeap):
               self.median = (self.maxHeap[0] + self.minHeap[0]) / 2
           else:
               self.median = self.maxHeap[0]
           print(self.median)

function RunningMedian(nums) {
   const maxHeap = [];
   const minHeap = [];
   let median = 0;
   for (let num of nums) {
       addNum(maxHeap, minHeap, num);
       balanceHeaps(maxHeap, minHeap);
       if (maxHeap.length === minHeap.length) {
           median = (maxHeap[0] + minHeap[0]) / 2;
       } else {
           median = maxHeap[0];
       }
       console.log(median);
   }
   function addNum(maxHeap, minHeap, num) {
       if (maxHeap.length === 0 || num < maxHeap[0]) {
           maxHeap.push(num);
           maxHeap.sort((a, b) => a - b);
       } else {
           minHeap.push(num);
           minHeap.sort((a, b) => a - b);
       }
       balanceHeaps(maxHeap, minHeap);
   }
   function balanceHeaps(maxHeap, minHeap) {
       if (maxHeap.length > minHeap.length + 1) {
           minHeap.push(maxHeap.pop());
           minHeap.sort((a, b) => a - b);
       } else if (minHeap.length > maxHeap.length) {
           maxHeap.push(minHeap.pop());
           maxHeap.sort((a, b) => a - b);
       }
   }
}

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Running Median Calculation Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Heap

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Running Median Calculation — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor