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.

Practice

1. What is the main idea behind finding the kth smallest element using a min heap?

easy

A. Use a hash map to count frequencies and find the kth smallest

B. Build a min heap from the array and extract the minimum element k times

C. Build a max heap and extract the maximum element k times

D. Sort the array and pick the element at index k

Solution

1. Step 1: Understand min heap property

   A min heap always keeps the smallest element at the root, so extracting the root gives the smallest element.

2. Step 2: Extract minimum k times

   By extracting the root k times, we get the kth smallest element.

3. Final Answer:

   Build a min heap and extract minimum k times -> Option B

4. Quick Check:

   Min heap extraction = kth smallest element [OK]

Hint: Extract min from min heap k times to get kth smallest [OK]

Common Mistakes:

• Using max heap instead of min heap
• Sorting array instead of using heap
• Extracting less or more than k times

2. Which of the following TypeScript code snippets correctly creates a min heap using a priority queue for numbers?

easy

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

B. const minHeap = new MinPriorityQueue<number>();

C. const minHeap = new PriorityQueue<number>((a, b) => b - a);

D. const minHeap = new MaxPriorityQueue<number>();

Solution

1. Step 1: Understand comparator for min heap

   A min heap comparator returns negative if first argument is smaller, so (a, b) => a - b is correct.

2. Step 2: Check code options

   const minHeap = new PriorityQueue<number>((a, b) => a - b); uses (a, b) => a - b, which creates a min heap. const minHeap = new PriorityQueue<number>((a, b) => b - a); reverses order, making max heap.

3. Final Answer:

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

4. Quick Check:

   Comparator a-b creates min heap [OK]

Hint: Use comparator (a, b) => a - b for min heap [OK]

Common Mistakes:

• Using max heap comparator for min heap
• Using wrong class name for min heap
• Confusing comparator logic

3. What will be the output of the following TypeScript code snippet?

const arr = [7, 10, 4, 3, 20, 15];
const k = 3;

// Build min heap
const minHeap = new MinPriorityQueue<number>();
arr.forEach(num => minHeap.enqueue(num));

let kthSmallest = -1;
for (let i = 0; i < k; i++) {
  kthSmallest = minHeap.dequeue().element;
}
console.log(kthSmallest);

medium

A. 7

B. 10

C. 3

D. 4

Solution

1. Step 1: Insert all elements into min heap

   Min heap will organize elements so smallest is at root: 3, 4, 7, 10, 15, 20.

2. Step 2: Extract min element k=3 times

   Extract 1: 3, Extract 2: 4, Extract 3: 7. So kth smallest is 7.

3. Final Answer:

   7 -> Option A

4. Quick Check:

   3rd smallest in array = 7 [OK]

Hint: Extract min k times from min heap to get kth smallest [OK]

Common Mistakes:

• Confusing kth smallest with kth largest
• Off-by-one error in loop
• Not building min heap correctly

4. Identify the bug in the following TypeScript code that tries to find the kth smallest element using a min heap:

function kthSmallest(arr: number[], k: number): number {
  const minHeap = new MinPriorityQueue<number>();
  for (let i = 0; i <= arr.length; i++) {
    minHeap.enqueue(arr[i]);
  }
  let result = -1;
  for (let j = 0; j < k; j++) {
    result = minHeap.dequeue().element;
  }
  return result;
}

medium

A. The dequeue loop should run k-1 times

B. MinPriorityQueue should be MaxPriorityQueue

C. Loop condition should be i < arr.length to avoid undefined enqueue

D. Return statement should be inside the loop

Solution

1. Step 1: Check array loop bounds

   The loop uses i <= arr.length, which accesses arr[arr.length] undefined, causing error.

2. Step 2: Correct loop condition

   Change to i < arr.length to avoid out-of-bounds access.

3. Final Answer:

   Loop condition should be i < arr.length to avoid undefined enqueue -> Option C

4. Quick Check:

   Array index out of bounds causes error [OK]

Hint: Use i < arr.length to avoid out-of-bounds errors [OK]

Common Mistakes:

• Using <= instead of < in loops
• Confusing min heap with max heap
• Incorrect dequeue loop count

5. Given a large array with many duplicate elements, which approach using a min heap is best to efficiently find the kth smallest unique element?

hard

A. Build a min heap from the array and extract k times ignoring duplicates during extraction

B. Sort the array and pick the kth element directly

C. Build a max heap of size k to track unique smallest elements

D. Use a hash set to filter unique elements first, then build a min heap

Solution

1. Step 1: Remove duplicates using a hash set

   Duplicates can cause incorrect counting of unique elements, so first filter unique elements.

2. Step 2: Build min heap from unique elements and extract kth smallest

   After filtering, build min heap and extract k times to get kth smallest unique element.

3. Final Answer:

   Use a hash set to filter unique elements first, then build a min heap -> Option D

4. Quick Check:

   Filter duplicates before heap for unique kth smallest [OK]

Hint: Filter duplicates first, then use min heap for kth unique smallest [OK]

Common Mistakes:

• Ignoring duplicates causing wrong kth element
• Using max heap incorrectly
• Extracting without filtering unique elements