Kth Smallest Element Using Min Heap in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Extraction

What is the output of the following C++ code that finds the 3rd smallest element using a min heap?

DSA C++

#include <iostream>
#include <vector>
#include <queue>

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

int main() {
    std::vector<int> nums = {7, 10, 4, 3, 20, 15};
    int k = 3;
    std::cout << kthSmallest(nums, k) << std::endl;
    return 0;
}

A 7

B 4

C 10

D 3

💡 Hint

Remember the min heap always pops the smallest element first.

The min heap sorts elements as 3, 4, 7, 10, 15, 20. The 3rd smallest element popped is 7.

❓ Predict Output

intermediate

Result of Kth Smallest Element with Duplicate Values

What will be the output of this code snippet finding the 4th smallest element using a min heap?

DSA C++

#include <iostream>
#include <vector>
#include <queue>

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

int main() {
    std::vector<int> nums = {5, 3, 3, 1, 2, 2};
    int k = 4;
    std::cout << kthSmallest(nums, k) << std::endl;
    return 0;
}

A 5

B 2

C 3

D 1

💡 Hint

Duplicates are included in the heap and count as separate elements.

The sorted order is 1, 2, 2, 3, 3, 5. The 4th smallest element is 3.

🧠 Conceptual

advanced

Time Complexity of Kth Smallest Element Using Min Heap

What is the time complexity of finding the kth smallest element in an array of size n using a min heap built from the entire array?

A O(n k)

B O(n log n)

C O(k log n)

D O(n + k log n)

💡 Hint

Building a heap from n elements takes linear time, then each pop takes log n time.

Building the min heap takes O(n). Extracting k elements takes O(k log n). Total is O(n + k log n).

🔧 Debug

advanced

Identify the Bug in Kth Smallest Element Code

What error will this code produce when trying to find the 2nd smallest element?

DSA C++

#include <iostream>
#include <vector>
#include <queue>

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

int main() {
    std::vector<int> nums = {8, 16, 4, 10};
    int k = 2;
    std::cout << kthSmallest(nums, k) << std::endl;
    return 0;
}

A The code outputs 10

B The code outputs 8

C The code outputs 4

D The code outputs 16

💡 Hint

Check the type of priority queue used and how it orders elements.

The priority_queue by default is a max heap, so top() returns the largest element. The 2nd largest is 10, not the 2nd smallest.

🚀 Application

expert

Kth Smallest Element in a Stream Using Min Heap

You want to maintain the kth smallest element in a stream of numbers arriving one by one. Which data structure and approach is best?

A Use a hash set to store all elements and find kth smallest by sorting the set each time

B Use a max heap of size k to store the k smallest elements seen so far; update on each new number

C Use a min heap of all elements seen so far; pop k times to find kth smallest after each insertion

D Use a sorted array and insert each new number in sorted order

💡 Hint

Keep only k elements to optimize time and space.

A max heap of size k keeps track of the k smallest elements efficiently. The top is the kth smallest. Min heap of all elements or sorting each time is inefficient.

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