Kth Smallest Element Using Min Heap in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a min heap from the given array.

DSA Typescript

const minHeap = new MinHeap();
for (const num of nums) {
  minHeap.[1](num);
}

Drag options to blanks, or click blank then click option'

Apush

Badd

Cinsert

Dappend

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'push' or 'append' which are array methods, not heap methods.

The method to add elements to a min heap is usually called 'insert'.

2fill in blank

medium

Complete the code to extract the smallest element from the min heap.

DSA Typescript

const smallest = minHeap.[1]();

Drag options to blanks, or click blank then click option'

AextractMin

Bpop

Cremove

Ddelete

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'pop' which removes the last element in an array, not the smallest in a heap.

The method to remove and return the smallest element in a min heap is 'extractMin'.

3fill in blank

hard

Fix the error in the loop that extracts k smallest elements from the min heap.

DSA Typescript

for (let i = 0; i < k; i++) {
  result.push(minHeap.[1]());
}

Drag options to blanks, or click blank then click option'

Apop

BextractMin

Cpeek

Dremove

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'peek' which does not remove elements, causing an infinite loop or repeated values.

To get the k smallest elements, we must extract the minimum each time using 'extractMin'.

4fill in blank

hard

Fill both blanks to complete the function that returns the kth smallest element using a min heap.

DSA Typescript

function kthSmallest(nums: number[], k: number): number {
  const minHeap = new MinHeap();
  for (const num of nums) {
    minHeap.[1](num);
  }
  let result = 0;
  for (let i = 0; i < k; i++) {
    result = minHeap.[2]();
  }
  return result;
}

Drag options to blanks, or click blank then click option'

Ainsert

BextractMin

Cpop

Dadd

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'pop' instead of 'extractMin' which does not guarantee smallest element removal.

We insert all numbers into the min heap, then extract the minimum k times to get the kth smallest.

5fill in blank

hard

Fill both blanks to complete the function that returns the kth smallest element using a min heap with early stopping.

DSA Typescript

function kthSmallest(nums: number[], k: number): number {
  const minHeap = new MinHeap();
  for (const num of nums) {
    minHeap.[1](num);
  }
  let result = 0;
  for (let i = 0; i < k; i++) {
    result = minHeap.[2]();
  }
  return result;
}

Drag options to blanks, or click blank then click option'

Ainsert

BextractMin

Cpop

Dadd

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'pop' which removes the last element, not the smallest.

Insert all numbers, then extract the minimum k times to get the kth smallest element.

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