Overview
Design a data structure that supports adding integers from a data stream and finding the median of all elements seen so far.
Implement the MedianFinder class:
addNum(num)— adds the integernumto the data structure.findMedian()— returns the median of all elements added so far. If the count is even, return the average of the two middle values.
Your solution will be tested by processing a list of operations.
Implement processMedianOps(operations) where each operation is ["addNum", num] or ["findMedian"], and return an array of results (null for addNum, the median for findMedian).
Constraints
-100000 ≤ num ≤ 100000- There will be at least one
addNumbefore anyfindMedian. findMedianmust run in $O(1)$ time.addNumshould run in $O(\log n)$ time.
Examples
processMedianOps([ ["addNum", 1], ["addNum", 2], ["findMedian"], // → 1.5 ["addNum", 3], ["findMedian"], // → 2 ]); // → [null, null, 1.5, null, 2]
Notes
- The classic approach uses two heaps: a max-heap for the lower half and a min-heap for the upper half.
- JavaScript has no built-in heap — you'll need to implement one or use sorted insertion.
- Balance the heaps so their sizes differ by at most 1. The median is either the top of the larger heap or the average of both tops.
Solution
Reveal solution
function processMedianOps(operations) {
// Simple sorted-array approach (O(n) insert, O(1) median)
const sorted = [];
const results = [];
function insert(arr, val) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] < val) lo = mid + 1;
else hi = mid;
}
arr.splice(lo, 0, val);
}
for (const op of operations) {
if (op[0] === "addNum") {
insert(sorted, op[1]);
results.push(null);
} else {
const n = sorted.length;
if (n % 2 === 1) {
results.push(sorted[Math.floor(n / 2)]);
} else {
results.push((sorted[n / 2 - 1] + sorted[n / 2]) / 2);
}
}
}
return results;
}Resources
Number Stream Median
Overview
Design a data structure that supports adding integers from a data stream and finding the median of all elements seen so far.
Implement the MedianFinder class:
addNum(num)— adds the integernumto the data structure.findMedian()— returns the median of all elements added so far. If the count is even, return the average of the two middle values.
Your solution will be tested by processing a list of operations.
Implement processMedianOps(operations) where each operation is ["addNum", num] or ["findMedian"], and return an array of results (null for addNum, the median for findMedian).
Constraints
-100000 ≤ num ≤ 100000- There will be at least one
addNumbefore anyfindMedian. findMedianmust run in $O(1)$ time.addNumshould run in $O(\log n)$ time.
Examples
processMedianOps([ ["addNum", 1], ["addNum", 2], ["findMedian"], // → 1.5 ["addNum", 3], ["findMedian"], // → 2 ]); // → [null, null, 1.5, null, 2]
Notes
- The classic approach uses two heaps: a max-heap for the lower half and a min-heap for the upper half.
- JavaScript has no built-in heap — you'll need to implement one or use sorted insertion.
- Balance the heaps so their sizes differ by at most 1. The median is either the top of the larger heap or the average of both tops.
Solution
Reveal solution
function processMedianOps(operations) {
// Simple sorted-array approach (O(n) insert, O(1) median)
const sorted = [];
const results = [];
function insert(arr, val) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] < val) lo = mid + 1;
else hi = mid;
}
arr.splice(lo, 0, val);
}
for (const op of operations) {
if (op[0] === "addNum") {
insert(sorted, op[1]);
results.push(null);
} else {
const n = sorted.length;
if (n % 2 === 1) {
results.push(sorted[Math.floor(n / 2)]);
} else {
results.push((sorted[n / 2 - 1] + sorted[n / 2]) / 2);
}
}
}
return results;
}