Kth Smallest Element Using Min Heap in DSA C++ - Time & Space Complexity

Time Complexity: Kth Smallest Element Using Min Heap

O(n + k log n)

Understanding Time Complexity

We want to understand how long it takes to find the kth smallest number using a min heap.

How does the time needed grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <queue>
#include <vector>

int kthSmallest(std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap(nums.begin(), nums.end());
    for (int i = 1; i < k; ++i) {
        minHeap.pop();
    }
    return minHeap.top();
}
    

This code builds a min heap from the list and removes the smallest element k-1 times to find the kth smallest.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Removing the smallest element from the min heap (pop operation).
• How many times: The pop operation repeats k-1 times.
• Building the min heap from the array happens once at the start.

How Execution Grows With Input

Building the heap takes time proportional to the size of the list, then each pop takes time related to the heap size.

Input Size (n)	Approx. Operations
10	Build heap ~ O(10), pop k-1 times (each ~ O(log 10))
100	Build heap ~ O(100), pop k-1 times (each ~ O(log 100))
1000	Build heap ~ O(1000), pop k-1 times (each ~ O(log 1000))

Pattern observation: Building heap grows linearly with n, popping grows with k times log n.

Final Time Complexity

Time Complexity: O(n + k log n)

This means the time grows mostly with the size of the list and the number of pops, each pop taking a bit longer as the list grows.

Common Mistake

[X] Wrong: "The time is just O(k) because we pop k times."

[OK] Correct: Each pop operation takes time related to the heap size (log n), not constant time, so total time depends on k times log n plus building the heap.

Interview Connect

Understanding this time complexity helps you explain why using a heap is efficient for finding the kth smallest element compared to sorting the whole list.

Self-Check

"What if we used a max heap of size k instead of a min heap of size n? How would the time complexity change?"

Practice

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

easy

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

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. Use a hash map to count frequencies and find the kth smallest

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
• Confusing kth smallest with kth largest

2. Which of the following C++ STL functions is used to create a min heap from a vector?

easy

A. std::make_heap(v.begin(), v.end(), std::greater<int>())

B. std::push_heap(v.begin(), v.end())

C. std::make_heap(v.begin(), v.end())

D. std::pop_heap(v.begin(), v.end())

Solution

1. Step 1: Understand default heap behavior

   By default, std::make_heap creates a max heap.

2. Step 2: Use comparator for min heap

   Passing std::greater<int>() as comparator creates a min heap.

3. Final Answer:

   std::make_heap with std::greater comparator -> Option A

4. Quick Check:

   std::make_heap + std::greater = min heap [OK]

Hint: Use std::greater<int>() with make_heap for min heap [OK]

Common Mistakes:

• Using default make_heap creates max heap
• Confusing push_heap and make_heap
• Using pop_heap to create heap

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

std::vector<int> v = {7, 10, 4, 3, 20, 15};
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap(v.begin(), v.end());
int k = 3;
int kthSmallest;
for (int i = 0; i < k; i++) {
    kthSmallest = minHeap.top();
    minHeap.pop();
}
std::cout << kthSmallest << std::endl;

medium

A. 10

B. 4

C. 7

D. 3

Solution

1. Step 1: Build min heap from vector

   The min heap elements in order of extraction are 3, 4, 7, 10, 15, 20.

2. Step 2: Extract min 3 times

   Extracted elements: 3 (1st), 4 (2nd), 7 (3rd). So, kth smallest (k=3) is 7.

3. Final Answer:

   7 -> Option C

4. Quick Check:

   3rd smallest element = 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 popping from heap after top

4. Identify the error in the following code to find the kth smallest element using a min heap:

std::vector<int> nums = {5, 3, 8, 4, 2};
std::priority_queue<int> minHeap(nums.begin(), nums.end());
int k = 2;
int result;
for (int i = 0; i < k; i++) {
    result = minHeap.top();
    minHeap.pop();
}
std::cout << result << std::endl;

medium

A. priority_queue creates max heap by default, not min heap

B. Loop should run k+1 times

C. pop() should be called before top()

D. Vector initialization syntax is incorrect

Solution

1. Step 1: Check priority_queue default behavior

   By default, std::priority_queue is a max heap, so it will give the largest element first.

2. Step 2: Effect on kth smallest extraction

   Extracting top k times from max heap gives kth largest, not kth smallest.

3. Final Answer:

   priority_queue creates max heap by default, not min heap -> Option A

4. Quick Check:

   Default priority_queue = max heap [OK]

Hint: Use comparator for min heap; default is max heap [OK]

Common Mistakes:

• Assuming priority_queue is min heap by default
• Wrong loop count for kth element
• Calling pop before top

5. Given a large unsorted array with possible duplicate elements, which approach using a min heap is most efficient to find the kth smallest unique element?

hard

A. Build a min heap of all elements and extract unique elements until kth unique is found

B. Sort the array and iterate to find kth unique element

C. Use a max heap of size k to track kth smallest unique element while iterating

D. Use a hash set to remove duplicates, then build min heap and extract kth element

Solution

1. Step 1: Remove duplicates using hash set

   Using a hash set removes duplicates efficiently, reducing the data size.

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

   Building min heap from unique elements and extracting kth smallest is efficient and correct.

3. Final Answer:

   Use a hash set to remove duplicates, then build min heap and extract kth element -> Option D

4. Quick Check:

   Remove duplicates first, then min heap extraction [OK]

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

Common Mistakes:

• Extracting kth smallest without removing duplicates
• Using max heap instead of min heap
• Sorting entire array unnecessarily