LeetCode: Find Median from Data Stream Solution

Approach

Approach 1 (sorting): sort the array on every insertion

Approach 2 (heap): insert but still keep the array sorted (efficient)

1var MedianFinder = function () {
2  this.arr = []
3}
4
5/**
6 * @param {number} num
7 * @return {void}
8 */
9MedianFinder.prototype.addNum = function (num) {
10  this.arr.push(num)
11  this.arr.sort((a, b) => a - b)
12}
13
14/**
15 * @return {number}
16 */
17MedianFinder.prototype.findMedian = function () {
18  const arrLength = this.arr.length
19  const midIndex = Math.floor(arrLength / 2)
20
21  if (arrLength % 2 === 0) {
22    return (this.arr[midIndex] + this.arr[midIndex - 1]) / 2
23  } else {
24    return this.arr[midIndex]
25  }
26}

Implementation (Heap)

1var MedianFinder = function () {
2  this.arr = []
3}
4
5/**
6 * @param {number} num
7 * @return {void}
8 */
9MedianFinder.prototype.addNum = function (num) {
10  let [left, right] = [0, this.arr.length - 1]
11  while (left <= right) {
12    let mid = Math.floor((left + right) / 2)
13    if (num >= this.arr[mid]) {
14      right = mid - 1
15    } else {
16      left = mid + 1
17    }
18  }
19  this.arr.splice(left, 0, num)
20}
21
22/**
23 * @return {number}
24 */
25MedianFinder.prototype.findMedian = function () {
26  const mid = Math.floor(this.arr.length / 2)
27  return this.arr.length % 2 === 0
28    ? (this.arr[mid - 1] + this.arr[mid]) / 2
29    : this.arr[mid]
30}