Kth Smallest Element Using Min Heap in DSA Typescript

Mental Model

A min heap always keeps the smallest element at the top, so we can remove the smallest elements one by one until we reach the kth smallest.

Analogy: Imagine a line of kids waiting to get ice cream, where the shortest kid is always at the front. To find the kth shortest kid, you let the first kid get ice cream and leave, then the next shortest moves to the front, and so on until you reach the kth kid.

Min Heap Array: [2, 3, 5, 7, 8, 10]
Heap structure:
      2
     / \
    3   5
   / \  /
  7  8 10
↑ (root is smallest)

Dry Run Walkthrough

Input: array: [7, 10, 4, 3, 20, 15], k=3

Goal: Find the 3rd smallest element in the array using a min heap

Step 1: Build min heap from array

Min Heap Array: [3, 7, 4, 10, 20, 15]
Heap structure:
      3
     / \
    7   4
   / \  /
  10 20 15

Why: We need the smallest element at the top to remove it easily

Step 2: Remove smallest element (3) from heap

Min Heap Array after removal: [4, 7, 15, 10, 20]
Heap structure:
      4
     / \
    7   15
   / \
  10 20

Why: Removing the smallest element moves us closer to the kth smallest

Step 3: Remove next smallest element (4) from heap

Min Heap Array after removal: [7, 10, 15, 20]
Heap structure:
      7
     / \
    10  15
   /
  20

Why: We continue removing smallest elements to reach the kth

Step 4: Remove next smallest element (7) from heap

Min Heap Array after removal: [10, 20, 15]
Heap structure:
      10
     / \
    20  15

Why: The 3rd removed element is the 3rd smallest in the array

Result:

Min Heap Array after 3 removals: [10, 20, 15]
The 3rd smallest element is 7

Annotated Code

DSA Typescript

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

  constructor(arr: number[]) {
    this.heap = arr.slice();
    this.buildHeap();
  }

  private buildHeap() {
    for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
      this.heapifyDown(i);
    }
  }

  private heapifyDown(i: number) {
    let smallest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
      smallest = left;
    }

    if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
      smallest = right;
    }

    if (smallest !== i) {
      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      this.heapifyDown(smallest);
    }
  }

  extractMin(): number | null {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0 && end !== undefined) {
      this.heap[0] = end;
      this.heapifyDown(0);
    }
    return min;
  }
}

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

// Driver code
const arr = [7, 10, 4, 3, 20, 15];
const k = 3;
const kth = kthSmallest(arr, k);
console.log(`${k}th smallest element is ${kth}`);

for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) { this.heapifyDown(i); }

Build min heap by heapifying from bottom non-leaf nodes up

if (this.heap.length === 0) return null;

Handle empty heap edge case before extraction

const min = this.heap[0];

Store smallest element at root to return

const end = this.heap.pop();

Remove last element to replace root

if (this.heap.length > 0 && end !== undefined) { this.heap[0] = end; this.heapifyDown(0); }

Replace root with last element and restore heap property

for (let i = 0; i < k; i++) { result = minHeap.extractMin(); if (result === null) return null; }

Extract min k times to get kth smallest element

Output

3th smallest element is 7

Complexity Analysis

Time: O(n + k log n) because building the heap takes O(n) and each of the k extractions takes O(log n)

Space: O(n) because the heap stores all elements of the array

vs Alternative: Compared to sorting the array which takes O(n log n), this method can be faster when k is small

Edge Cases

k is larger than array length

Function returns null because kth smallest does not exist

DSA Typescript

if (result === null) return null;

empty array

Function returns null immediately

DSA Typescript

if (this.heap.length === 0) return null;

array with duplicate elements

Duplicates are treated normally; kth smallest counts duplicates as separate elements

DSA Typescript

No special guard needed; heap handles duplicates naturally

When to Use This Pattern

When you need the kth smallest or largest element efficiently, and the data is unsorted, reach for the min heap pattern because it lets you remove smallest elements quickly without full sorting.

Common Mistakes

Mistake: Extracting min fewer than k times and returning wrong element
Fix: Ensure to extract min exactly k times to get the kth smallest

Mistake: Not rebuilding heap after extraction
Fix: After removing root, replace it with last element and heapify down to restore heap property

Summary

Finds the kth smallest element by building a min heap and extracting the smallest element k times.

Use when you want the kth smallest element without sorting the entire array.

The smallest element is always at the root of the min heap, so repeated extraction leads to the kth smallest.

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