Kth Smallest Element Using Min Heap in DSA Typescript - Execution Trace

Concept Flow - Kth Smallest Element Using Min Heap

Build Min Heap from array

↓

Extract min element k-1 times

↓

Heap root is kth smallest

↓

Return root value

Build a min heap from the array, then remove the smallest element k-1 times. The root after these removals is the kth smallest.

Execution Sample

DSA Typescript

function kthSmallest(arr: number[], k: number): number {
  const minHeap = new MinHeap(arr);
  for (let i = 1; i < k; i++) {
    minHeap.extractMin();
  }
  return minHeap.getMin();
}

Find kth smallest by building a min heap and extracting min k-1 times, then returning the root.

Execution Table

Step	Operation	Nodes in Heap	Pointer Changes	Visual State
1	Build Min Heap from [7, 10, 4, 3, 20, 15]	[3, 7, 4, 10, 20, 15]	Heapify rearranged nodes	3 -> 7 -> 4 -> 10 -> 20 -> 15
2	Extract Min (1st extraction)	[4, 7, 15, 10, 20]	Root 3 removed, last element 20 moved to root, heapify down	4 -> 7 -> 15 -> 10 -> 20
3	Extract Min (2nd extraction)	[7, 10, 15, 20]	Root 4 removed, last element 20 moved to root, heapify down	7 -> 10 -> 15 -> 20
4	Return root as 3rd smallest	[7, 10, 15, 20]	No pointer change	7 -> 10 -> 15 -> 20

💡 After 2 extractions (k-1), root is kth smallest element 7

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
Heap Array	[7,10,4,3,20,15]	[3,7,4,10,20,15]	[4,7,15,10,20]	[7,10,15,20]	[7,10,15,20]
Heap Size	6	6	5	4	4
Extracted Elements	[]	[]	[3]	[3,4]	[3,4]
Current Root	7	3	4	7	7

Key Moments - 3 Insights

Why do we extract min k-1 times instead of k times?

Because after removing the smallest element k-1 times, the root of the heap is the kth smallest. Extracting k times would remove the kth smallest itself.

Why does the heap change after each extraction?

After removing the root, the last element moves to root and heapify rearranges nodes to maintain min heap property, as shown in steps 2 and 3.

Why is the initial heap root 3 and not 4 or 7?

Heapify rearranges the array so the smallest element is at the root, which is 3 in step 1, ensuring min heap property.

Visual Quiz - 3 Questions

Look at the execution table, what is the heap root after the first extraction?

A 3

B 4

C 7

D 15

💡 Hint

Check Step 2 in execution_table under 'Current Root' and 'Visual State'

At which step does the heap size become 4?

A After Step 3

B After Step 2

C After Step 1

D After Step 4

💡 Hint

Look at variable_tracker row 'Heap Size' for changes after each step

If k was 2 instead of 3, what would be the kth smallest element returned?

A 3

B 7

C 4

D 10

💡 Hint

Refer to execution_table rows for extractions and root values after k-1 removals

Concept Snapshot

Kth Smallest Using Min Heap:
- Build min heap from array
- Extract min element k-1 times
- Root after extractions is kth smallest
- Extraction removes smallest and heapify restores order
- Time: O(n + k log n) for heap operations

Full Transcript

To find the kth smallest element using a min heap, first build a min heap from the input array. This organizes the data so the smallest element is at the root. Then, extract the minimum element k-1 times, each time removing the root and re-heapifying to maintain the heap property. After these extractions, the root of the heap is the kth smallest element. This method efficiently finds the kth smallest without sorting the entire array.

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