Median of Data Stream Using Two Heaps in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Median After Adding Numbers

What is the median after adding the numbers 5, 15, 1, 3 in order using two heaps?

DSA Javascript

class MedianFinder {
  constructor() {
    this.small = [] // max heap
    this.large = [] // min heap
  }

  addNum(num) {
    if (this.small.length === 0 || num <= -this.small[0]) {
      this.small.push(-num)
      this.small.sort((a, b) => a - b)
    } else {
      this.large.push(num)
      this.large.sort((a, b) => a - b)
    }

    if (this.small.length > this.large.length + 1) {
      this.large.push(-this.small.shift())
      this.large.sort((a, b) => a - b)
    } else if (this.large.length > this.small.length) {
      this.small.push(-this.large.shift())
      this.small.sort((a, b) => a - b)
    }
  }

  findMedian() {
    if (this.small.length > this.large.length) {
      return -this.small[0]
    } else {
      return (-this.small[0] + this.large[0]) / 2
    }
  }
}

const mf = new MedianFinder()
mf.addNum(5)
mf.addNum(15)
mf.addNum(1)
mf.addNum(3)
const median = mf.findMedian()
console.log(median)

A 4

B 3

C 5

D 6

💡 Hint

Think about how the two heaps balance the numbers and how median is calculated from their tops.

After adding 5 and 15, median is (5+15)/2 = 10. After adding 1, median is 5. After adding 3, numbers are [1,3,5,15], median is (3+5)/2 = 4.

🧠 Conceptual

intermediate

Why Use Two Heaps for Median of Data Stream?

Why do we use two heaps (a max heap and a min heap) to find the median in a data stream?

A To store all numbers twice for redundancy.

B To sort all numbers in ascending order efficiently.

C To use one heap for odd numbers and one for even numbers.

D To keep track of the lower half and upper half of numbers separately for quick median calculation.

💡 Hint

Think about how median relates to the middle values in a sorted list.

Two heaps split the data stream into lower half (max heap) and upper half (min heap). This allows quick access to middle values for median calculation.

🔧 Debug

advanced

Identify the Bug in MedianFinder Implementation

What error will this code produce when adding numbers and finding median?

DSA Javascript

class MedianFinder {
  constructor() {
    this.small = [] // max heap
    this.large = [] // min heap
  }

  addNum(num) {
    if (this.small.length === 0 || num <= -this.small[0]) {
      this.small.push(-num)
      this.small.sort((a, b) => a - b)
    } else {
      this.large.push(num)
      this.large.sort((a, b) => a - b)
    }

    if (this.small.length > this.large.length + 1) {
      this.large.push(-this.small.shift())
      this.large.sort((a, b) => a - b)
    } else if (this.large.length > this.small.length) {
      this.small.push(-this.large.shift())
      this.small.sort((a, b) => a - b)
    }
  }

  findMedian() {
    if (this.small.length > this.large.length) {
      return -this.small[0]
    } else {
      return (-this.small[0] + this.large[0]) / 2
    }
  }
}

const mf = new MedianFinder()
mf.addNum(1)
mf.addNum(2)
mf.addNum(3)
console.log(mf.findMedian())

A The code runs correctly and outputs 2

B The code outputs 1.5 instead of 2

C The code throws a TypeError because shift() is used on a sorted array without heap structure

D The code throws a SyntaxError due to missing semicolons

💡 Hint

Think about how shift() affects the heap property after sorting.

The code uses arrays and sorts them to simulate heaps but uses shift() which removes the first element, breaking the heap property. This causes incorrect behavior or errors.

📝 Syntax

advanced

Which Option Fixes the Heap Balancing Logic?

Given the buggy code below, which option correctly fixes the balancing logic to maintain heaps properly? class MedianFinder { constructor() { this.small = [] // max heap this.large = [] // min heap } addNum(num) { if (this.small.length === 0 || num <= -this.small[0]) { this.small.push(-num) this.small.sort() } else { this.large.push(num) this.large.sort() } if (this.small.length > this.large.length + 1) { this.large.push(-this.small.shift()) this.large.sort() } else if (this.large.length > this.small.length) { this.small.push(-this.large.shift()) this.small.sort() } } findMedian() { if (this.small.length > this.large.length) { return -this.small[0] } else { return (-this.small[0] + this.large[0]) / 2 } } }

A Replace shift() with pop() and use a proper heap data structure instead of sorting arrays.

B Remove all sorting calls and rely on push() only.

C Use unshift() instead of push() to add elements to arrays.

D Replace push() with concat() to add elements.

💡 Hint

Think about how heaps work and how to maintain their properties.

Heaps require specific operations like push and pop with heapify. Using shift() and sorting arrays breaks heap properties. Using pop() with a proper heap fixes this.

🚀 Application

expert

Calculate Median After Complex Stream Operations

Given the following sequence of numbers added to the MedianFinder: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, what is the median after all insertions?

DSA Javascript

class MedianFinder {
  constructor() {
    this.small = [] // max heap
    this.large = [] // min heap
  }

  addNum(num) {
    if (this.small.length === 0 || num <= -this.small[0]) {
      this.small.push(-num)
      this.small.sort((a, b) => a - b)
    } else {
      this.large.push(num)
      this.large.sort((a, b) => a - b)
    }

    if (this.small.length > this.large.length + 1) {
      this.large.push(-this.small.shift())
      this.large.sort((a, b) => a - b)
    } else if (this.large.length > this.small.length) {
      this.small.push(-this.large.shift())
      this.small.sort((a, b) => a - b)
    }
  }

  findMedian() {
    if (this.small.length > this.large.length) {
      return -this.small[0]
    } else {
      return (-this.small[0] + this.large[0]) / 2
    }
  }
}

const mf = new MedianFinder()
[10,20,30,40,50,60,70,80,90,100].forEach(n => mf.addNum(n))
console.log(mf.findMedian())

A 60

B 55

C 50

D 65

💡 Hint

Count the numbers and find the middle two values for even count.

There are 10 numbers, so median is average of 5th and 6th numbers in sorted order: (50 + 60)/2 = 55.

Practice

1. What is the main purpose of using two heaps (a max-heap and a min-heap) when finding the median of a data stream?

easy

A. To sort all numbers in ascending order

B. To efficiently keep track of the lower half and upper half of the numbers separately

C. To store all numbers in a single data structure

D. To find the maximum number in the data stream

Solution

1. Step 1: Understand the role of two heaps

   The max-heap stores the smaller half of the numbers, and the min-heap stores the larger half.

2. Step 2: Explain how this helps find the median

   By balancing these heaps, the median is either the top of one heap or the average of the tops of both heaps.

3. Final Answer:

   To efficiently keep track of the lower half and upper half of the numbers separately -> Option B

4. Quick Check:

   Two heaps split data halves = A [OK]

Hint: Two heaps split data halves for median [OK]

Common Mistakes:

• Thinking heaps sort all numbers fully
• Using only one heap for median
• Confusing max-heap and min-heap roles

2. Which of the following is the correct way to insert a number into the two heaps when maintaining the median in JavaScript?

easy

A. Always insert into min-heap

B. Always insert into max-heap

C. Insert into max-heap if number is less than or equal to max-heap root; else insert into min-heap

D. Insert randomly into either heap

Solution

1. Step 1: Decide heap based on number value

   If the number is smaller or equal to the max-heap root, it belongs to the lower half, so insert into max-heap.

2. Step 2: Otherwise insert into min-heap

   If the number is greater, it belongs to the upper half, so insert into min-heap.

3. Final Answer:

   Insert into max-heap if number is less than or equal to max-heap root; else insert into min-heap -> Option C

4. Quick Check:

   Compare with max-heap root to choose heap [OK]

Hint: Compare with max-heap root to choose heap [OK]

Common Mistakes:

• Inserting all numbers into one heap
• Not comparing with max-heap root
• Inserting randomly without condition

3. Consider the following JavaScript code snippet using two heaps to find the median after inserting numbers 5, 15, 1, 3:

const maxHeap = new MaxHeap();
const minHeap = new MinHeap();

function addNum(num) {
  if (maxHeap.size() === 0 || num <= maxHeap.peek()) {
    maxHeap.insert(num);
  } else {
    minHeap.insert(num);
  }

  if (maxHeap.size() > minHeap.size() + 1) {
    minHeap.insert(maxHeap.extract());
  } else if (minHeap.size() > maxHeap.size()) {
    maxHeap.insert(minHeap.extract());
  }
}

addNum(5);
addNum(15);
addNum(1);
addNum(3);

const median = maxHeap.size() > minHeap.size() ? maxHeap.peek() : (maxHeap.peek() + minHeap.peek()) / 2;
console.log(median);

What is the output printed?

medium

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5 into maxHeap (empty). Insert 15 into minHeap (15 > 5). Insert 1 into maxHeap (1 <= 5). Insert 3 into maxHeap (3 <= 5). Now maxHeap has 3 elements, minHeap has 1.

2. Step 2: Balance heaps sizes

   maxHeap size (3) > minHeap size (1) + 1, so move maxHeap.extract() (which is 5) to minHeap. Now maxHeap has [3,1], minHeap has [5,15]. Median is average of maxHeap.peek()=3 and minHeap.peek()=5, so (3+5)/2 = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Median after balancing = 4 [OK]

Hint: Balance heaps sizes, median is middle or average [OK]

Common Mistakes:

• Not balancing heaps after insertion
• Taking median as maxHeap.peek() only
• Incorrect heap extraction order

4. The following code snippet is intended to maintain the median using two heaps, but it has a bug:

function addNum(num) {
  if (num < maxHeap.peek()) {
    maxHeap.insert(num);
  } else {
    minHeap.insert(num);
  }

  if (maxHeap.size() > minHeap.size() + 1) {
    minHeap.insert(maxHeap.extract());
  } else if (minHeap.size() > maxHeap.size()) {
    maxHeap.insert(minHeap.extract());
  }
}

What is the bug in this code?

medium

A. It inserts all numbers into minHeap

B. It uses > instead of >= in the size comparison

C. It balances heaps incorrectly by moving elements the wrong way

D. It does not handle the case when maxHeap is empty before peek()

Solution

1. Step 1: Identify peek() usage problem

   The code calls maxHeap.peek() without checking if maxHeap is empty, causing an error on first insertion.

2. Step 2: Explain impact of missing empty check

   Without checking, calling peek() on empty maxHeap throws an error, so the first number cannot be inserted properly.

3. Final Answer:

   It does not handle the case when maxHeap is empty before peek() -> Option D

4. Quick Check:

   Empty maxHeap peek() causes error [OK]

Hint: Check heap empty before peek() to avoid errors [OK]

Common Mistakes:

• Ignoring empty heap before peek()
• Assuming heaps always balanced before insert
• Incorrect size comparison operators

5. You are given a stream of numbers: [2, 4, 7, 1, 5, 3]. Using two heaps (max-heap for lower half, min-heap for upper half), what is the median after inserting all numbers? Also, explain why balancing the heaps is important in this process.

hard

A. 3.5; Balancing keeps heaps sizes equal or off by one to find median correctly

B. 4; Balancing is not necessary if we always insert correctly

C. 3; Balancing helps to sort the entire stream

D. 5; Balancing is used to find max value quickly

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 2 (maxHeap empty, goes to maxHeap). Insert 4 (4 > 2, minHeap). Insert 7 (7 > 2, minHeap). Now minHeap has 2 elements, maxHeap 1, so move minHeap.extract() (4) to maxHeap. Insert 1 (1 <= 4, maxHeap). Insert 5 (5 > 4, minHeap). Insert 3 (3 <= 4, maxHeap). Heaps are balanced with maxHeap size 4 and minHeap size 2, move maxHeap.extract() (4) to minHeap to balance sizes.

2. Step 2: Calculate median and explain balancing

   Now maxHeap has [3,2,1] with peek()=3, minHeap has [4,5,7] with peek()=4. Since sizes equal (3 and 3), median is (3 + 4)/2 = 3.5. Balancing keeps heaps sizes equal or off by one to find median correctly from the tops.

3. Final Answer:

   3.5; Balancing keeps heaps sizes equal or off by one to find median correctly -> Option A

4. Quick Check:

   Balanced heaps give median 3.5 [OK]

Hint: Balance heaps sizes to get median from tops [OK]

Common Mistakes:

• Not balancing heaps after each insertion
• Calculating median from unsorted data
• Confusing median with max or min values