295. Find Median from Data Stream

1. Two heaps (max-heap + min-heap)

Maintain a max-heap for the lower half and a min-heap for the upper half. Keep them balanced (sizes differ by at most 1). Median is the top of the larger heap, or the average of both tops.

Time

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

Space

O(n)

// JavaScript has no built-in heap. Simulate with sorted insertion for interview.
// For production: implement a binary heap or use a library.
class MedianFinder {
  constructor() {
    // lo = max-heap (negate values to simulate with min-heap logic)
    // hi = min-heap
    this.lo = []; // lower half, stored negated for max-heap simulation
    this.hi = []; // upper half
  }

  _pushMaxHeap(val) {
    // Insert into sorted lo array (descending order)
    let lo = 0, hi = this.lo.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.lo[mid] < val) hi = mid; else lo = mid + 1;
    }
    this.lo.splice(lo, 0, val);
  }

  _pushMinHeap(val) {
    let lo = 0, hi = this.hi.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.hi[mid] > val) hi = mid; else lo = mid + 1;
    }
    this.hi.splice(lo, 0, val);
  }

  addNum(num) {
    // Always push to lo first, then rebalance
    this._pushMaxHeap(num);
    // Balance: lo's max must be <= hi's min
    if (this.hi.length && this.lo[0] > this.hi[0]) {
      this._pushMinHeap(this.lo.shift());
    }
    // Size invariant: lo can have at most 1 more than hi
    if (this.lo.length > this.hi.length + 1) {
      this._pushMinHeap(this.lo.shift());
    } else if (this.hi.length > this.lo.length) {
      this._pushMaxHeap(this.hi.shift());
    }
  }

  findMedian() {
    if (this.lo.length > this.hi.length) return this.lo[0];
    return (this.lo[0] + this.hi[0]) / 2;
  }
}

Tradeoff: The interview explanation uses real heaps. Since JS lacks a built-in binary heap, explain the heap logic verbally and note that in production you'd implement a proper binary heap (O(log n) push/pop). The code above uses sorted arrays for clarity — real O(log n) requires a heap implementation. Citadel expects you to know the heap logic even if the language makes it harder to implement directly.