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.

Practice

1. What is the main purpose of using two heaps (a max heap and a min heap) in the Median of Data Stream problem?

easy

A. To sort all numbers in ascending order

B. To store all numbers in a single data structure

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

D. To remove duplicates from 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 tops of both heaps.

3. Final Answer:

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

4. Quick Check:

   Two heaps split data halves = efficient median [OK]

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

Common Mistakes:

• Thinking heaps sort all numbers fully
• Using one heap only
• Confusing heaps with arrays

2. Which TypeScript syntax correctly declares a max heap using a priority queue for numbers?

easy

A. const maxHeap = new PriorityQueue<number>((a, b) => b - a);

B. const maxHeap = new PriorityQueue<number>((a, b) => a - b);

C. const maxHeap = new PriorityQueue<number>();

D. const maxHeap = new PriorityQueue<number>((a, b) => a + b);

Solution

1. Step 1: Understand max heap comparator

   Max heap comparator returns positive if first is less than second, so b - a creates max heap.

2. Step 2: Check each option

   const maxHeap = new PriorityQueue<number>((a, b) => b - a); uses (b - a) which is correct for max heap; others do not create max heap order.

3. Final Answer:

   const maxHeap = new PriorityQueue<number>((a, b) => b - a); -> Option A

4. Quick Check:

   Comparator b - a = max heap [OK]

Hint: Max heap comparator subtracts first from second [OK]

Common Mistakes:

• Using a - b for max heap (creates min heap)
• Not providing comparator
• Using addition in comparator

3. Given the following sequence of numbers inserted into the data stream: [5, 15, 1, 3], what is the median after all insertions using two heaps?

medium

A. 3

B. 4

C. 5

D. 8

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5 -> maxHeap=[5] (top=5), minHeap=[]; Insert 15 -> minHeap=[15] (top=15), sizes 1:1; Insert 1 -> maxHeap=[5,1] (top=5), sizes 2:1; Insert 3 -> maxHeap=[5,3,1] (top=5), sizes 3:1 -> balance (max.size > min.size+1), move max.top=5 to minHeap -> maxHeap=[3,1] (top=3), minHeap=[5,15] (top=5), sizes 2:2.

2. Step 2: Calculate median from heaps

   Sizes equal, median = (maxHeap.top + minHeap.top)/2 = (3 + 5)/2 = 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Median of [5,15,1,3] = 4 [OK]

Hint: Median is average of two heap tops if sizes equal [OK]

Common Mistakes:

• Taking median as top of one heap only
• Not balancing heaps after insertion
• Wrong average calculation

4. Consider this TypeScript snippet for adding a number to the data stream median finder:

if (num <= maxHeap.peek()) {
  maxHeap.enqueue(num);
} else {
  minHeap.enqueue(num);
}

// Balance heaps
if (maxHeap.size() > minHeap.size() + 1) {
  minHeap.enqueue(maxHeap.dequeue());
} else if (minHeap.size() > maxHeap.size()) {
  maxHeap.enqueue(minHeap.dequeue());
}

What is the bug in this code?

medium

A. It compares num with minHeap.peek() instead of maxHeap.peek()

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

C. It uses enqueue instead of push for heaps

D. It does not handle empty maxHeap before peek() call

Solution

1. Step 1: Analyze peek() usage on maxHeap

   If maxHeap is empty, calling peek() causes error because no element exists yet.

2. Step 2: Identify missing empty check

   Code should check if maxHeap is empty before peek() or handle initial insertion separately.

3. Final Answer:

   It does not handle empty maxHeap before peek() call -> Option D

4. Quick Check:

   Empty heap peek() causes runtime error [OK]

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

Common Mistakes:

• Assuming heaps always have elements
• Mixing enqueue and push methods
• Balancing heaps incorrectly

5. You want to extend the Median of Data Stream solution to support removing numbers from the stream efficiently. Which data structure modification is best to support both insertion and removal while maintaining median calculation?

hard

A. Use two heaps with a hash map to mark removed elements lazily

B. Use two balanced binary search trees (like AVL or Red-Black trees) instead of heaps

C. Use a single sorted array and binary search for insertion and removal

D. Use two queues to store lower and upper halves

Solution

1. Step 1: Understand removal challenge in heaps

   Heaps do not support efficient arbitrary removal, so direct removal is costly.

2. Step 2: Explain lazy removal with hash map

   Mark elements as removed in a hash map and skip them during heap operations to simulate removal efficiently.

3. Step 3: Compare other options

   Balanced trees support removal but are more complex; arrays are inefficient; queues do not maintain order.

4. Final Answer:

   Use two heaps with a hash map to mark removed elements lazily -> Option A

5. Quick Check:

   Lazy removal with hash map + heaps = efficient median update [OK]

Hint: Lazy removal with hash map keeps heaps efficient [OK]

Common Mistakes:

• Trying direct removal from heaps
• Using arrays causing slow operations
• Ignoring complexity of balanced trees