LeetCode: Find Median from Data Stream Solution

Insert and keep the array sorted

Approach

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

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

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}var MedianFinder = function () {2  this.arr = []3}4
5/**6 * @param {number} num7 * @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.length19  const midIndex = Math.floor(arrLength / 2)20
21  if (arrLength % 2 === 0) {22    return (this.arr[midIndex] + this.arr[midIndex - 1]) / 223  } else {24    return this.arr[midIndex]25  }26}```

Implementation (Heap)

```1var MedianFinder = function () {2  this.arr = []3}4
5/**6 * @param {number} num7 * @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 - 115    } else {16      left = mid + 117    }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 === 028    ? (this.arr[mid - 1] + this.arr[mid]) / 229    : this.arr[mid]30}```

leetcode

sorting

heap

Next Post

LeetCode: Isomorphic Strings

Jul 12, 2021

Use 2 hash tables

Previous Post

LeetCode: Longest Increasing Subsequence

Jul 9, 2021

Dynamic programming, top-down approach

Search Posts