Kth Smallest Element Using Min Heap in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Extraction

What is the output of the following TypeScript code that finds the 3rd smallest element using a min heap?

DSA Typescript

class MinHeap {
  heap: number[] = [];

  insert(val: number) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] <= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  extractMin(): number | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
    const min = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.bubbleDown();
    return min;
  }

  bubbleDown() {
    let index = 0;
    const length = this.heap.length;
    while (true) {
      let left = 2 * index + 1;
      let right = 2 * index + 2;
      let smallest = index;

      if (left < length && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < length && this.heap[right] < this.heap[smallest]) smallest = right;
      if (smallest === index) break;

      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }
}

function kthSmallest(arr: number[], k: number): number | undefined {
  const minHeap = new MinHeap();
  for (const num of arr) {
    minHeap.insert(num);
  }
  let result: number | undefined;
  for (let i = 0; i < k; i++) {
    result = minHeap.extractMin();
  }
  return result;
}

const arr = [7, 10, 4, 3, 20, 15];
const k = 3;
console.log(kthSmallest(arr, k));

A 4

B 3

C 7

D 10

💡 Hint

Remember the min heap always extracts the smallest element first.

The min heap extracts elements in ascending order: 3, 4, 7, 10, 15, 20. The 3rd smallest is 7.

🧠 Conceptual

intermediate

Understanding Min Heap Property

Which statement correctly describes the min heap property used in finding the kth smallest element?

A The root node is always the smallest element in the heap.

B The root node is always the largest element in the heap.

C All leaf nodes are smaller than their parents.

D The heap is always sorted in ascending order internally.

💡 Hint

Think about what element you get when you extract from a min heap.

In a min heap, the smallest element is always at the root, allowing quick access to the minimum.

🔧 Debug

advanced

Identify the Bug in Kth Smallest Using Min Heap

What error will occur when running this code snippet to find the 4th smallest element?

DSA Typescript

function kthSmallestBug(arr: number[], k: number): number {
  const minHeap = new MinHeap();
  for (const num of arr) {
    minHeap.insert(num);
  }
  let result = 0;
  for (let i = 0; i <= k; i++) {
    result = minHeap.extractMin()!;
  }
  return result;
}

const arr = [5, 3, 8];
console.log(kthSmallestBug(arr, 4));

A Returns 0 incorrectly

B Runtime error: Cannot read property of undefined

C Returns 8 correctly

D Syntax error due to missing semicolon

💡 Hint

Check the loop boundary and array size.

The loop runs one extra time (i <= k) causing extractMin to return undefined when heap is empty, leading to runtime error.

🚀 Application

advanced

Using Min Heap to Find Kth Smallest in a Stream

You receive a stream of numbers and want to find the 2nd smallest number at any time using a min heap. Which approach is best?

A Insert all numbers into a min heap and extract min twice each time you want the 2nd smallest.

B Sort the stream each time a new number arrives and pick the 2nd element.

C Maintain a min heap of all numbers and peek the root for the smallest number only.

D Maintain a max heap of size 2 with the smallest numbers seen so far.

💡 Hint

Think about efficiency when the stream is large and continuous.

Maintaining a max heap of size k keeps track of the k smallest elements efficiently, allowing quick access to the kth smallest.

❓ Predict Output

expert

Output of Kth Smallest with Duplicate Elements

What is the output of this code finding the 4th smallest element in an array with duplicates?

DSA Typescript

const arr = [2, 1, 2, 1, 3];
const k = 4;

function kthSmallestWithDuplicates(arr: number[], k: number): number | undefined {
  const minHeap = new MinHeap();
  for (const num of arr) {
    minHeap.insert(num);
  }
  let result: number | undefined;
  for (let i = 0; i < k; i++) {
    result = minHeap.extractMin();
  }
  return result;
}

console.log(kthSmallestWithDuplicates(arr, k));

A 2

B 3

C 1

D undefined

💡 Hint

Duplicates are counted as separate elements in the heap.

The sorted order with duplicates is 1, 1, 2, 2, 3. The 4th smallest is 2.