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.