Kth Smallest Element Using Min Heap in DSA Typescript - Build from Scratch

Kth Smallest Element Using Min Heap

📖 Scenario: Imagine you have a list of numbers representing the scores of players in a game. You want to find the kth smallest score to see who is just above a certain rank.

🎯 Goal: You will build a program that uses a min heap to find the kth smallest element in a list of numbers.

📋 What You'll Learn

Create an array called scores with the exact numbers: [20, 15, 8, 10, 5, 7, 6]

Create a variable called k and set it to 3

Use a min heap to find the kth smallest element in scores

Print the kth smallest element

💡 Why This Matters

🌍 Real World

Finding the kth smallest element is useful in ranking systems, like finding the player who is just above a certain position.

💼 Career

Understanding heaps and sorting is important for software engineers working on algorithms, data processing, and performance optimization.

1

Create the scores array

Create an array called scores with these exact numbers: [20, 15, 8, 10, 5, 7, 6]

DSA Typescript

// Create the scores array
// Your code here

Hint

Use const scores = [20, 15, 8, 10, 5, 7, 6]; to create the array.

2

Set the value of k

Create a variable called k and set it to 3

DSA Typescript

const scores = [20, 15, 8, 10, 5, 7, 6];
// Create variable k and set it to 3
// Your code here

Hint

Use const k = 3; to set the value.

3

Find the kth smallest element using a min heap

Use a min heap by sorting the scores array in ascending order and then get the element at index k - 1. Store this element in a variable called kthSmallest

DSA Typescript

const scores = [20, 15, 8, 10, 5, 7, 6];
const k = 3;
// Sort scores and get kth smallest element
// Your code here

Hint

Use scores.slice().sort((a, b) => a - b) to create a sorted copy of the array.

Then get the element at k - 1 index.

4

Print the kth smallest element

Print the value of kthSmallest using console.log

DSA Typescript

const scores = [20, 15, 8, 10, 5, 7, 6];
const k = 3;
const sortedScores = scores.slice().sort((a, b) => a - b);
const kthSmallest = sortedScores[k - 1];
// Print kthSmallest
// Your code here

Hint

Use console.log(kthSmallest); to print the result.

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