The main idea is to use a max-heap to store the smaller half of the numbers and a min-heap to store the larger half. The max-heap allows you to efficiently fetch the largest element of the smaller half, and the min-heap allows you to efficiently fetch the smallest element of the larger half. To maintain the balance, ensure that the number of elements in the max-heap is either equal to or one more than the number of elements in the min-heap.
The time complexity for adding a number is O(log n) due to heap adjustments. Finding the median has a time complexity of O(1). Space complexity is O(n), where n is the number of elements.
1class MedianFinder {
2 constructor() {
3 this.small = new MinHeap(); // Max-Heap
4 this.large = new MinHeap(); // Min-Heap
5 }
6 addNum(num) {
7 this.small.insert(-num);
8 if (-this.small.peek() > this.large.peek()) {
9 this.large.insert(-this.small.remove());
10 }
11 if (this.small.size() > this.large.size() + 1) {
12 this.large.insert(-this.small.remove());
13 }
14 if (this.large.size() > this.small.size()) {
15 this.small.insert(-this.large.remove());
16 }
17 }
18 findMedian() {
19 if (this.small.size() > this.large.size()) return -this.small.peek();
20 return (-this.small.peek() + this.large.peek()) / 2.0;
21 }
22}
23
24class MinHeap {
25 constructor() {
26 this.heap = [];
27 }
28 insert(val) {
29 this.heap.push(val);
30 this._bubbleUp();
31 }
32 peek() {
33 return this.heap[0] || Infinity;
34 }
35 remove() {
36 if (this.size() < 2) return this.heap.pop() || Infinity;
37 this._swap(0, this.heap.length - 1);
38 const popped = this.heap.pop();
39 this._bubbleDown();
40 return popped;
41 }
42 size() {
43 return this.heap.length;
44 }
45 _bubbleUp() {
46 let idx = this.heap.length - 1;
47 const element = this.heap[idx];
48 while (idx > 0) {
49 let parentIdx = Math.floor((idx - 1) / 2);
50 let parent = this.heap[parentIdx];
51 if (element >= parent) break;
52 this._swap(parentIdx, idx);
53 idx = parentIdx;
54 }
55 }
56 _bubbleDown() {
57 let idx = 0;
58 const length = this.heap.length;
59 const element = this.heap[0];
60 while (true) {
61 let leftIdx = 2 * idx + 1;
62 let rightIdx = 2 * idx + 2;
63 let left, right;
64 let swap = null;
65 if (leftIdx < length) {
66 left = this.heap[leftIdx];
67 if (left < element) swap = leftIdx;
68 }
69 if (rightIdx < length) {
70 right = this.heap[rightIdx];
71 if ((swap === null && right < element) || (swap !== null && right < left)) swap = rightIdx;
72 }
73 if (swap === null) break;
74 this._swap(idx, swap);
75 idx = swap;
76 }
77 }
78 _swap(i, j) {
79 [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
80 }
81}In this JavaScript solution, two heaps are used to separate lower and upper halves. A custom MinHeap class was implemented for heap operations. The program balances heaps after every insertion, then computes the median based on heap sizes.
An alternative approach is to use a balanced binary search tree (BST) to keep track of the numbers. This allows maintaining a sorted order of elements, which can make finding the median efficient since a BST can give average-case time complexity of O(log n) for insertion and O(1) for median finding.
Insertion and balancing in the sorted set take O(log n) time, and findings of the median are O(1). Space complexity is O(n).
1using System;
2using System.Collections.Generic;
3
4public class MedianFinder {
5 private SortedSet<(int, int)> small;
6 private SortedSet<(int, int)> large;
7 private int counter = 0;
8
9 public MedianFinder() {
10 small = new SortedSet<(int, int)>();
11 large = new SortedSet<(int, int)>();
12 }
13
14 public void AddNum(int num) {
15 small.Add((num, counter++));
16 large.Add(small.Max);
17 small.Remove(small.Max);
18 if (large.Count > small.Count) {
19 small.Add(large.Min);
20 large.Remove(large.Min);
21 }
22 }
23
24 public double FindMedian() {
25 if (small.Count > large.Count) {
26 return small.Max.Item1;
27 }
28 return (small.Max.Item1 + large.Min.Item1) / 2.0;
29 }
30}This C# implementation uses two sorted sets as a stand-in for a balanced BST. Every number is inserted into the smaller set first, followed by balancing between the two sets. The median is retrieved based on the sizes of the sets and their boundary values.