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

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the median after inserting these numbers?

Given a data stream where numbers are inserted one by one, what is the median after inserting the sequence [5, 15, 1, 3] using two heaps (a max heap for the lower half and a min heap for the upper half)?

DSA Typescript

Insert 5
Insert 15
Insert 1
Insert 3
Find median

A 6

B 4

C 5

D 3

💡 Hint

Balance the heaps so their sizes differ by at most one and the max heap contains the smaller half.

After inserting 5, median is 5.
After 15, median is (5+15)/2 = 10.
After 1, median is 5.
After 3, median is (3+5)/2 = 4.

🧠 Conceptual

intermediate

Why use two heaps to find median in a data stream?

What is the main reason for using two heaps (a max heap and a min heap) to find the median in a data stream?

A To store all elements twice for redundancy

B To sort all elements in ascending order efficiently

C To keep the smaller half in max heap and larger half in min heap for quick median access

D To use heaps as queues for faster insertion

💡 Hint

Think about how median relates to halves of sorted data.

The two heaps split the data into smaller and larger halves. The max heap stores the smaller half so its root is the largest of the smaller numbers. The min heap stores the larger half so its root is the smallest of the larger numbers. This allows quick median calculation.

🔧 Debug

advanced

Identify the error in this median update code

What error will occur when running this TypeScript code snippet for updating heaps after inserting a new number in the data stream?

DSA Typescript

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

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

A Runtime error because maxHeap.peek() may be undefined when maxHeap is empty

B No error, code runs correctly

C Logical error: heaps are never balanced

D Syntax error due to missing semicolon

💡 Hint

Consider what happens when maxHeap is empty and peek() is called.

If maxHeap is empty, calling peek() returns undefined or throws an error. Comparing num > undefined causes a runtime error.

❓ Predict Output

advanced

What is the median after these insertions?

Using two heaps, what is the median after inserting the numbers [10, 20, 30, 40, 50] in order?

DSA Typescript

Insert 10
Insert 20
Insert 30
Insert 40
Insert 50
Find median

A 35

B 25

C 20

D 30

💡 Hint

Balance heaps so their sizes differ by at most one and median is root of max heap when odd count.

After inserting all numbers, the median is the middle number 30.

🧠 Conceptual

expert

What is the time complexity of finding median using two heaps?

What is the time complexity for inserting a number and finding the median in a data stream using two heaps?

A Insertion: O(log n), Median retrieval: O(1)

B Insertion: O(n), Median retrieval: O(log n)

C Insertion: O(1), Median retrieval: O(n)

D Insertion: O(n log n), Median retrieval: O(1)

💡 Hint

Consider heap insertion and peek operations.

Insertion into a heap takes O(log n) time. Median retrieval is O(1) because it is the root of one or both heaps.