295. Find median

295_solution1_intuitive.c

#include <stdbool.h>
#include <stdlib.h>

typedef struct {
  int *data;
  int size;
  int cap;
  bool isMax;
} Heap;

// true if a must sit above b
static bool before(const Heap *h, int a, int b) {
  return h->isMax ? a > b : a < b;
}

static void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

static void push(Heap *h, int val) {
  if (h->size == h->cap) {
    h->cap = h->cap ? 2 * h->cap : 16;
    h->data = realloc(h->data, h->cap * sizeof(int));
  }
  int *d = h->data, i = h->size++;
  d[i] = val;
  while (i > 0 && before(h, d[i], d[(i - 1) / 2])) {
    swap(&d[i], &d[(i - 1) / 2]);
    i = (i - 1) / 2;
  }
}

static int pop(Heap *h) {
  int *d = h->data, top = d[0], i = 0;
  d[0] = d[--h->size];
  for (;;) {
    int best = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < h->size && before(h, d[l], d[best]))
      best = l;
    if (r < h->size && before(h, d[r], d[best]))
      best = r;
    if (best == i)
      return top;
    swap(&d[best], &d[i]);
    i = best;
  }
}

typedef struct {
  Heap maxHeap; // left half
  Heap minHeap; // right half
} MedianFinder;

MedianFinder *medianFinderCreate() {
  MedianFinder *obj = calloc(1, sizeof(MedianFinder));
  obj->maxHeap.isMax = true;
  return obj;
}

void medianFinderAddNum(MedianFinder *obj, int num) {
  Heap *lo = &obj->maxHeap, *hi = &obj->minHeap;

  if (hi->size > 0 && num >= hi->data[0])
    push(hi, num);
  else
    push(lo, num);

  if (lo->size > hi->size + 1)
    push(hi, pop(lo));

  if (hi->size > lo->size)
    push(lo, pop(hi));
}

double medianFinderFindMedian(MedianFinder *obj) {
  Heap *lo = &obj->maxHeap, *hi = &obj->minHeap;
  if ((lo->size + hi->size) % 2 == 0)
    return (lo->data[0] + hi->data[0]) / 2.0;
  return lo->data[0];
}

void medianFinderFree(MedianFinder *obj) {
  free(obj->maxHeap.data);
  free(obj->minHeap.data);
  free(obj);
}

295_solution2_compact.c

#include <stdbool.h>
#include <stdlib.h>

typedef struct {
  int *data;
  int size;
  int cap;
  bool isMax;
} Heap;

// true if a must sit above b
static bool before(const Heap *h, int a, int b) {
  return h->isMax ? a > b : a < b;
}

static void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

static void push(Heap *h, int val) {
  if (h->size == h->cap) {
    h->cap = h->cap ? 2 * h->cap : 16;
    h->data = realloc(h->data, h->cap * sizeof(int));
  }
  int *d = h->data, i = h->size++;
  d[i] = val;
  while (i > 0 && before(h, d[i], d[(i - 1) / 2])) {
    swap(&d[i], &d[(i - 1) / 2]);
    i = (i - 1) / 2;
  }
}

static int pop(Heap *h) {
  int *d = h->data, top = d[0], i = 0;
  d[0] = d[--h->size];
  for (;;) {
    int best = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < h->size && before(h, d[l], d[best]))
      best = l;
    if (r < h->size && before(h, d[r], d[best]))
      best = r;
    if (best == i)
      return top;
    swap(&d[best], &d[i]);
    i = best;
  }
}

typedef struct {
  Heap lo; // max-heap, lower half
  Heap hi; // min-heap, upper half
} MedianFinder;

MedianFinder *medianFinderCreate() {
  MedianFinder *obj = calloc(1, sizeof(MedianFinder));
  obj->lo.isMax = true;
  return obj;
}

void medianFinderAddNum(MedianFinder *obj, int num) {
  push(&obj->lo, num);
  push(&obj->hi, pop(&obj->lo));
  if (obj->hi.size > obj->lo.size)
    push(&obj->lo, pop(&obj->hi));
}

double medianFinderFindMedian(MedianFinder *obj) {
  if (obj->lo.size > obj->hi.size)
    return obj->lo.data[0];
  return (obj->lo.data[0] + obj->hi.data[0]) / 2.0;
}

void medianFinderFree(MedianFinder *obj) {
  free(obj->lo.data);
  free(obj->hi.data);
  free(obj);
}

295_followup1.c

#include <stdlib.h>

typedef struct {
  int cnt[101];
  int total;
} MedianFinder;

static int kth(const MedianFinder *obj, int k) { // k-th smallest, 1-indexed
  int seen = 0;
  for (int v = 0; v <= 100; v++) {
    seen += obj->cnt[v];
    if (seen >= k)
      return v;
  }
  return -1; // unreachable if 1 <= k <= total
}

MedianFinder *medianFinderCreate() { return calloc(1, sizeof(MedianFinder)); }

void medianFinderAddNum(MedianFinder *obj, int num) {
  obj->cnt[num]++;
  obj->total++;
}

double medianFinderFindMedian(MedianFinder *obj) {
  int a = kth(obj, (obj->total + 1) / 2);
  int b = kth(obj, obj->total / 2 + 1);
  return (a + b) / 2.0;
}

void medianFinderFree(MedianFinder *obj) { free(obj); }

295_followup2.c

#include <stdlib.h>

typedef struct {
  int cnt[101];
  int below; // numbers < 0
  int above; // numbers > 100
  int total;
} MedianFinder;

static int kth(const MedianFinder *obj, int k) {
  int seen = obj->below; // outliers below the range come first in sorted order
  for (int v = 0; v <= 100; v++) {
    seen += obj->cnt[v];
    if (seen >= k)
      return v;
  }
  return -1;
}

MedianFinder *medianFinderCreate() { return calloc(1, sizeof(MedianFinder)); }

void medianFinderAddNum(MedianFinder *obj, int num) {
  if (num < 0)
    obj->below++;
  else if (num > 100)
    obj->above++;
  else
    obj->cnt[num]++;
  obj->total++;
}

double medianFinderFindMedian(MedianFinder *obj) {
  int a = kth(obj, (obj->total + 1) / 2);
  int b = kth(obj, obj->total / 2 + 1);
  return (a + b) / 2.0;
}

void medianFinderFree(MedianFinder *obj) { free(obj); }

295_solution1_intuitive.cpp

#include <functional>
#include <queue>
#include <vector>

using namespace std;

class MedianFinder {
private:
  priority_queue<int> maxHeap;                            // left half
  priority_queue<int, vector<int>, greater<int>> minHeap; // right half
public:
  MedianFinder() {}

  void addNum(int num) {
    if (!minHeap.empty() && num >= minHeap.top())
      minHeap.push(num);
    else
      maxHeap.push(num);

    if (maxHeap.size() > minHeap.size() + 1) {
      minHeap.push(maxHeap.top());
      maxHeap.pop();
    }

    if (minHeap.size() > maxHeap.size()) {
      maxHeap.push(minHeap.top());
      minHeap.pop();
    }
  }

  double findMedian() {
    if ((minHeap.size() + maxHeap.size()) % 2 == 0)
      return (minHeap.top() + maxHeap.top()) / 2.0;
    else
      return maxHeap.top();
  }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

295_solution2_compact.cpp

#include <functional>
#include <queue>
#include <vector>

using namespace std;

class MedianFinder {
  priority_queue<int> lo;                            // max-heap, lower half
  priority_queue<int, vector<int>, greater<int>> hi; // min-heap, upper half

public:
  void addNum(int num) {
    lo.push(num);
    hi.push(lo.top());
    lo.pop();
    if (hi.size() > lo.size()) {
      lo.push(hi.top());
      hi.pop();
    }
  }

  double findMedian() {
    if (lo.size() > hi.size())
      return lo.top();
    return (lo.top() + hi.top()) / 2.0;
  }
};

295_followup1.cpp

class MedianFinder {
  int cnt[101] = {};
  int total = 0;

  int kth(int k) { // k-th smallest, 1-indexed
    int seen = 0;
    for (int v = 0; v <= 100; v++) {
      seen += cnt[v];
      if (seen >= k)
        return v;
    }
    return -1; // unreachable if 1 <= k <= total
  }

public:
  void addNum(int num) {
    cnt[num]++;
    total++;
  }

  double findMedian() {
    int a = kth((total + 1) / 2);
    int b = kth(total / 2 + 1);
    return (a + b) / 2.0;
  }
};

295_followup2.cpp

class MedianFinder {
  int cnt[101] = {};
  int below = 0; // numbers < 0
  int above = 0; // numbers > 100
  int total = 0;

  int kth(int k) {
    int seen = below; // outliers below the range come first in sorted order
    for (int v = 0; v <= 100; v++) {
      seen += cnt[v];
      if (seen >= k)
        return v;
    }
    return -1;
  }

public:
  void addNum(int num) {
    if (num < 0)
      below++;
    else if (num > 100)
      above++;
    else
      cnt[num]++;
    total++;
  }

  double findMedian() {
    int a = kth((total + 1) / 2);
    int b = kth(total / 2 + 1);
    return (a + b) / 2.0;
  }
};

295_solution1_intuitive.go

package heaps

import (
    "container/heap"
    "sort"
)

type minHeap struct{ sort.IntSlice }

func (h *minHeap) Push(x any) { h.IntSlice = append(h.IntSlice, x.(int)) }

func (h *minHeap) Pop() any {
    old := h.IntSlice
    x := old[len(old)-1]
    h.IntSlice = old[:len(old)-1]
    return x
}

func (h *minHeap) top() int { return h.IntSlice[0] }

type maxHeap struct{ minHeap }

func (h maxHeap) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }

type MedianFinder struct {
    maxHeap *maxHeap // left half
    minHeap *minHeap // right half
}

func Constructor() MedianFinder {
    return MedianFinder{&maxHeap{}, &minHeap{}}
}

func (this *MedianFinder) AddNum(num int) {
    if this.minHeap.Len() > 0 && num >= this.minHeap.top() {
        heap.Push(this.minHeap, num)
    } else {
        heap.Push(this.maxHeap, num)
    }

    if this.maxHeap.Len() > this.minHeap.Len()+1 {
        heap.Push(this.minHeap, heap.Pop(this.maxHeap))
    }

    if this.minHeap.Len() > this.maxHeap.Len() {
        heap.Push(this.maxHeap, heap.Pop(this.minHeap))
    }
}

func (this *MedianFinder) FindMedian() float64 {
    if (this.minHeap.Len()+this.maxHeap.Len())%2 == 0 {
        return float64(this.minHeap.top()+this.maxHeap.top()) / 2
    }
    return float64(this.maxHeap.top())
}

295_solution2_compact.go

package heaps

import (
    "container/heap"
    "sort"
)

type minHeap struct{ sort.IntSlice }

func (h *minHeap) Push(x any) { h.IntSlice = append(h.IntSlice, x.(int)) }

func (h *minHeap) Pop() any {
    old := h.IntSlice
    x := old[len(old)-1]
    h.IntSlice = old[:len(old)-1]
    return x
}

func (h *minHeap) top() int { return h.IntSlice[0] }

type maxHeap struct{ minHeap }

func (h maxHeap) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }

type MedianFinder struct {
    lo *maxHeap // lower half
    hi *minHeap // upper half
}

func Constructor() MedianFinder {
    return MedianFinder{&maxHeap{}, &minHeap{}}
}

func (this *MedianFinder) AddNum(num int) {
    heap.Push(this.lo, num)
    heap.Push(this.hi, heap.Pop(this.lo))
    if this.hi.Len() > this.lo.Len() {
        heap.Push(this.lo, heap.Pop(this.hi))
    }
}

func (this *MedianFinder) FindMedian() float64 {
    if this.lo.Len() > this.hi.Len() {
        return float64(this.lo.top())
    }
    return float64(this.lo.top()+this.hi.top()) / 2
}

295_followup1.go

package heaps

type MedianFinder struct {
    cnt   [101]int
    total int
}

func Constructor() MedianFinder {
    return MedianFinder{}
}

func (this *MedianFinder) kth(k int) int { // k-th smallest, 1-indexed
    seen := 0
    for v := 0; v <= 100; v++ {
        seen += this.cnt[v]
        if seen >= k {
            return v
        }
    }
    return -1 // unreachable if 1 <= k <= total
}

func (this *MedianFinder) AddNum(num int) {
    this.cnt[num]++
    this.total++
}

func (this *MedianFinder) FindMedian() float64 {
    a := this.kth((this.total + 1) / 2)
    b := this.kth(this.total/2 + 1)
    return float64(a+b) / 2
}

295_followup2.go

package heaps

type MedianFinder struct {
    cnt   [101]int
    below int // numbers < 0
    above int // numbers > 100
    total int
}

func Constructor() MedianFinder {
    return MedianFinder{}
}

func (this *MedianFinder) kth(k int) int {
    seen := this.below // outliers below the range come first in sorted order
    for v := 0; v <= 100; v++ {
        seen += this.cnt[v]
        if seen >= k {
            return v
        }
    }
    return -1
}

func (this *MedianFinder) AddNum(num int) {
    switch {
    case num < 0:
        this.below++
    case num > 100:
        this.above++
    default:
        this.cnt[num]++
    }
    this.total++
}

func (this *MedianFinder) FindMedian() float64 {
    a := this.kth((this.total + 1) / 2)
    b := this.kth(this.total/2 + 1)
    return float64(a+b) / 2
}

295_solution1_intuitive.java

import java.util.Collections;
import java.util.PriorityQueue;

class MedianFinder {
    private final PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // left half
    private final PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // right half

    public void addNum(int num) {
        if (!minHeap.isEmpty() && num >= minHeap.peek())
            minHeap.offer(num);
        else
            maxHeap.offer(num);

        if (maxHeap.size() > minHeap.size() + 1)
            minHeap.offer(maxHeap.poll());

        if (minHeap.size() > maxHeap.size())
            maxHeap.offer(minHeap.poll());
    }

    public double findMedian() {
        if ((minHeap.size() + maxHeap.size()) % 2 == 0)
            return (minHeap.peek() + maxHeap.peek()) / 2.0;
        return maxHeap.peek();
    }
}

295_solution2_compact.java

import java.util.Collections;
import java.util.PriorityQueue;

class MedianFinder {
    private final PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()); // lower half
    private final PriorityQueue<Integer> hi = new PriorityQueue<>(); // upper half

    public void addNum(int num) {
        lo.offer(num);
        hi.offer(lo.poll());
        if (hi.size() > lo.size())
            lo.offer(hi.poll());
    }

    public double findMedian() {
        if (lo.size() > hi.size())
            return lo.peek();
        return (lo.peek() + hi.peek()) / 2.0;
    }
}

295_followup1.java

class MedianFinder {
    private final int[] cnt = new int[101];
    private int total = 0;

    private int kth(int k) { // k-th smallest, 1-indexed
        int seen = 0;
        for (int v = 0; v <= 100; v++) {
            seen += cnt[v];
            if (seen >= k)
                return v;
        }
        return -1; // unreachable if 1 <= k <= total
    }

    public void addNum(int num) {
        cnt[num]++;
        total++;
    }

    public double findMedian() {
        int a = kth((total + 1) / 2);
        int b = kth(total / 2 + 1);
        return (a + b) / 2.0;
    }
}

295_followup2.java

class MedianFinder {
    private final int[] cnt = new int[101];
    private int below = 0; // numbers < 0
    private int above = 0; // numbers > 100
    private int total = 0;

    private int kth(int k) {
        int seen = below; // outliers below the range come first in sorted order
        for (int v = 0; v <= 100; v++) {
            seen += cnt[v];
            if (seen >= k)
                return v;
        }
        return -1;
    }

    public void addNum(int num) {
        if (num < 0)
            below++;
        else if (num > 100)
            above++;
        else
            cnt[num]++;
        total++;
    }

    public double findMedian() {
        int a = kth((total + 1) / 2);
        int b = kth(total / 2 + 1);
        return (a + b) / 2.0;
    }
}

295_solution1_intuitive.js

class Heap {
  // cmp(a, b) < 0 means a comes out first
  constructor(cmp) {
    this.cmp = cmp;
    this.data = [];
  }

  top() {
    return this.data[0];
  }

  size() {
    return this.data.length;
  }

  push(val) {
    const h = this.data;
    h.push(val);
    let i = h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.cmp(h[p], h[i]) <= 0) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  }

  pop() {
    const h = this.data;
    const top = h[0];
    const last = h.pop();
    if (h.length === 0) return top;
    h[0] = last;
    let i = 0;
    for (;;) {
      let best = i;
      const l = 2 * i + 1,
        r = 2 * i + 2;
      if (l < h.length && this.cmp(h[l], h[best]) < 0) best = l;
      if (r < h.length && this.cmp(h[r], h[best]) < 0) best = r;
      if (best === i) return top;
      [h[best], h[i]] = [h[i], h[best]];
      i = best;
    }
  }
}

class MedianFinder {
  constructor() {
    this.maxHeap = new Heap((a, b) => b - a); // left half
    this.minHeap = new Heap((a, b) => a - b); // right half
  }

  addNum(num) {
    if (this.minHeap.size() > 0 && num >= this.minHeap.top()) this.minHeap.push(num);
    else this.maxHeap.push(num);

    if (this.maxHeap.size() > this.minHeap.size() + 1) this.minHeap.push(this.maxHeap.pop());

    if (this.minHeap.size() > this.maxHeap.size()) this.maxHeap.push(this.minHeap.pop());
  }

  findMedian() {
    if ((this.minHeap.size() + this.maxHeap.size()) % 2 === 0)
      return (this.minHeap.top() + this.maxHeap.top()) / 2;
    return this.maxHeap.top();
  }
}

295_solution2_compact.js

class Heap {
  // cmp(a, b) < 0 means a comes out first
  constructor(cmp) {
    this.cmp = cmp;
    this.data = [];
  }

  top() {
    return this.data[0];
  }

  size() {
    return this.data.length;
  }

  push(val) {
    const h = this.data;
    h.push(val);
    let i = h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.cmp(h[p], h[i]) <= 0) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  }

  pop() {
    const h = this.data;
    const top = h[0];
    const last = h.pop();
    if (h.length === 0) return top;
    h[0] = last;
    let i = 0;
    for (;;) {
      let best = i;
      const l = 2 * i + 1,
        r = 2 * i + 2;
      if (l < h.length && this.cmp(h[l], h[best]) < 0) best = l;
      if (r < h.length && this.cmp(h[r], h[best]) < 0) best = r;
      if (best === i) return top;
      [h[best], h[i]] = [h[i], h[best]];
      i = best;
    }
  }
}

class MedianFinder {
  constructor() {
    this.lo = new Heap((a, b) => b - a); // max-heap, lower half
    this.hi = new Heap((a, b) => a - b); // min-heap, upper half
  }

  addNum(num) {
    this.lo.push(num);
    this.hi.push(this.lo.pop());
    if (this.hi.size() > this.lo.size()) this.lo.push(this.hi.pop());
  }

  findMedian() {
    if (this.lo.size() > this.hi.size()) return this.lo.top();
    return (this.lo.top() + this.hi.top()) / 2;
  }
}

295_followup1.js

class MedianFinder {
  constructor() {
    this.cnt = new Array(101).fill(0);
    this.total = 0;
  }

  // k-th smallest, 1-indexed
  kth(k) {
    let seen = 0;
    for (let v = 0; v <= 100; v++) {
      seen += this.cnt[v];
      if (seen >= k) return v;
    }
    return -1; // unreachable if 1 <= k <= total
  }

  addNum(num) {
    this.cnt[num]++;
    this.total++;
  }

  findMedian() {
    const a = this.kth(Math.floor((this.total + 1) / 2));
    const b = this.kth(Math.floor(this.total / 2) + 1);
    return (a + b) / 2;
  }
}

295_followup2.js

class MedianFinder {
  constructor() {
    this.cnt = new Array(101).fill(0);
    this.below = 0; // numbers < 0
    this.above = 0; // numbers > 100
    this.total = 0;
  }

  kth(k) {
    let seen = this.below; // outliers below the range come first in sorted order
    for (let v = 0; v <= 100; v++) {
      seen += this.cnt[v];
      if (seen >= k) return v;
    }
    return -1;
  }

  addNum(num) {
    if (num < 0) this.below++;
    else if (num > 100) this.above++;
    else this.cnt[num]++;
    this.total++;
  }

  findMedian() {
    const a = this.kth(Math.floor((this.total + 1) / 2));
    const b = this.kth(Math.floor(this.total / 2) + 1);
    return (a + b) / 2;
  }
}

295_solution1_intuitive.py

import heapq


class MedianFinder:
    def __init__(self):
        self.max_heap: list[int] = []  # left half, negated
        self.min_heap: list[int] = []  # right half

    def addNum(self, num: int) -> None:
        if self.min_heap and num >= self.min_heap[0]:
            heapq.heappush(self.min_heap, num)
        else:
            heapq.heappush(self.max_heap, -num)

        if len(self.max_heap) > len(self.min_heap) + 1:
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))

        if len(self.min_heap) > len(self.max_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def findMedian(self) -> float:
        if (len(self.min_heap) + len(self.max_heap)) % 2 == 0:
            return (self.min_heap[0] - self.max_heap[0]) / 2
        return -self.max_heap[0]

295_solution2_compact.py

import heapq


class MedianFinder:
    def __init__(self):
        self.lo: list[int] = []  # max-heap (negated), lower half
        self.hi: list[int] = []  # min-heap, upper half

    def addNum(self, num: int) -> None:
        heapq.heappush(self.hi, -heapq.heappushpop(self.lo, -num))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self) -> float:
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (self.hi[0] - self.lo[0]) / 2

295_followup1.py

class MedianFinder:
    def __init__(self):
        self.cnt = [0] * 101
        self.total = 0

    def _kth(self, k: int) -> int:  # k-th smallest, 1-indexed
        seen = 0
        for v in range(101):
            seen += self.cnt[v]
            if seen >= k:
                return v
        return -1  # unreachable if 1 <= k <= total

    def addNum(self, num: int) -> None:
        self.cnt[num] += 1
        self.total += 1

    def findMedian(self) -> float:
        a = self._kth((self.total + 1) // 2)
        b = self._kth(self.total // 2 + 1)
        return (a + b) / 2

295_followup2.py

class MedianFinder:
    def __init__(self):
        self.cnt = [0] * 101
        self.below = 0  # numbers < 0
        self.above = 0  # numbers > 100
        self.total = 0

    def _kth(self, k: int) -> int:
        seen = self.below  # outliers below the range come first in sorted order
        for v in range(101):
            seen += self.cnt[v]
            if seen >= k:
                return v
        return -1

    def addNum(self, num: int) -> None:
        if num < 0:
            self.below += 1
        elif num > 100:
            self.above += 1
        else:
            self.cnt[num] += 1
        self.total += 1

    def findMedian(self) -> float:
        a = self._kth((self.total + 1) // 2)
        b = self._kth(self.total // 2 + 1)
        return (a + b) / 2

295_solution1_intuitive.rs

use std::cmp::Reverse;
use std::collections::BinaryHeap;

struct MedianFinder {
    max_heap: BinaryHeap<i32>,          // left half
    min_heap: BinaryHeap<Reverse<i32>>, // right half
}

impl MedianFinder {
    fn new() -> Self {
        Self { max_heap: BinaryHeap::new(), min_heap: BinaryHeap::new() }
    }

    fn add_num(&mut self, num: i32) {
        match self.min_heap.peek() {
            Some(&Reverse(top)) if num >= top => self.min_heap.push(Reverse(num)),
            _ => self.max_heap.push(num),
        }

        if self.max_heap.len() > self.min_heap.len() + 1 {
            let top = self.max_heap.pop().unwrap();
            self.min_heap.push(Reverse(top));
        }

        if self.min_heap.len() > self.max_heap.len() {
            let Reverse(top) = self.min_heap.pop().unwrap();
            self.max_heap.push(top);
        }
    }

    fn find_median(&self) -> f64 {
        let lo = *self.max_heap.peek().unwrap() as f64;
        if (self.min_heap.len() + self.max_heap.len()) % 2 == 0 {
            (lo + self.min_heap.peek().unwrap().0 as f64) / 2.0
        } else {
            lo
        }
    }
}

295_solution2_compact.rs

use std::cmp::Reverse;
use std::collections::BinaryHeap;

struct MedianFinder {
    lo: BinaryHeap<i32>,          // max-heap, lower half
    hi: BinaryHeap<Reverse<i32>>, // min-heap, upper half
}

impl MedianFinder {
    fn new() -> Self {
        Self { lo: BinaryHeap::new(), hi: BinaryHeap::new() }
    }

    fn add_num(&mut self, num: i32) {
        self.lo.push(num);
        self.hi.push(Reverse(self.lo.pop().unwrap()));
        if self.hi.len() > self.lo.len() {
            self.lo.push(self.hi.pop().unwrap().0);
        }
    }

    fn find_median(&self) -> f64 {
        let lo = *self.lo.peek().unwrap() as f64;
        if self.lo.len() > self.hi.len() {
            return lo;
        }
        (lo + self.hi.peek().unwrap().0 as f64) / 2.0
    }
}

295_followup1.rs

struct MedianFinder {
    cnt: [i32; 101],
    total: i32,
}

impl MedianFinder {
    fn new() -> Self {
        Self { cnt: [0; 101], total: 0 }
    }

    // k-th smallest, 1-indexed
    fn kth(&self, k: i32) -> i32 {
        let mut seen = 0;
        for v in 0..=100 {
            seen += self.cnt[v];
            if seen >= k {
                return v as i32;
            }
        }
        -1 // unreachable if 1 <= k <= total
    }

    fn add_num(&mut self, num: i32) {
        self.cnt[num as usize] += 1;
        self.total += 1;
    }

    fn find_median(&self) -> f64 {
        let a = self.kth((self.total + 1) / 2);
        let b = self.kth(self.total / 2 + 1);
        (a + b) as f64 / 2.0
    }
}

295_followup2.rs

struct MedianFinder {
    cnt: [i32; 101],
    below: i32, // numbers < 0
    above: i32, // numbers > 100
    total: i32,
}

impl MedianFinder {
    fn new() -> Self {
        Self { cnt: [0; 101], below: 0, above: 0, total: 0 }
    }

    fn kth(&self, k: i32) -> i32 {
        let mut seen = self.below; // outliers below the range come first in sorted order
        for v in 0..=100 {
            seen += self.cnt[v];
            if seen >= k {
                return v as i32;
            }
        }
        -1
    }

    fn add_num(&mut self, num: i32) {
        if num < 0 {
            self.below += 1;
        } else if num > 100 {
            self.above += 1;
        } else {
            self.cnt[num as usize] += 1;
        }
        self.total += 1;
    }

    fn find_median(&self) -> f64 {
        let a = self.kth((self.total + 1) / 2);
        let b = self.kth(self.total / 2 + 1);
        (a + b) as f64 / 2.0
    }
}