Kth Smallest Element Using Min Heap in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a min heap from the vector.

DSA C++

std::priority_queue<int, std::vector<int>, [1]> minHeap(nums.begin(), nums.end());

Drag options to blanks, or click blank then click option'

Astd::greater<int>

Bstd::less<int>

Cstd::equal_to<int>

Dstd::not_equal_to<int>

Attempts:

3 left

💡 Hint

Common Mistakes

Using std::less creates a max heap, not a min heap.

Forgetting to specify the comparator leads to max heap behavior.

The min heap in C++ priority_queue is created by using std::greater<int> as the comparison function.

2fill in blank

medium

Complete the code to pop the smallest element from the min heap.

DSA C++

minHeap.[1]();

Drag options to blanks, or click blank then click option'

Aremove

Bdelete

Cpop

Dextract

Attempts:

3 left

💡 Hint

Common Mistakes

Using remove or delete which are not valid methods for priority_queue.

Trying to erase elements by value instead of popping the top.

Use pop() to remove the top (smallest) element from the priority_queue.

3fill in blank

hard

Fix the error in the code to get the kth smallest element from the min heap.

DSA C++

for (int i = 1; i < [1]; ++i) {
    minHeap.pop();
}
return minHeap.top();

Drag options to blanks, or click blank then click option'

Ak

Bk-1

Ck*2

Dk+1

Attempts:

3 left

💡 Hint

Common Mistakes

Using k-1 in the loop condition causes one less pop than needed.

Using k+1 or k*2 causes too many pops and wrong result.

We pop (k-1) times to remove the first (k-1) smallest elements, then the top is the kth smallest. The loop runs from 1 to k-1, so condition is i < k.

4fill in blank

hard

Fill both blanks to complete the function that returns the kth smallest element using a min heap.

DSA C++

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

Drag options to blanks, or click blank then click option'

Astd::greater<int>

Bk

Ck-1

Dstd::less<int>

Attempts:

3 left

💡 Hint

Common Mistakes

Using std::less creates max heap, wrong for kth smallest.

Looping until i < k-1 pops too few elements.

The min heap uses std::greater<int>. The loop runs while i < k to pop (k-1) elements.

5fill in blank

hard

Fill all three blanks to create a function that returns the kth smallest element using a min heap and handles empty input.

DSA C++

int kthSmallest(std::vector<int>& nums, int k) {
    if (nums.empty() || k > nums.size()) return -1;
    std::priority_queue<int, std::vector<int>, [1]> minHeap(nums.begin(), nums.end());
    for (int i = 1; i < [2]; ++i) {
        minHeap.[3]();
    }
    return minHeap.top();
}

Drag options to blanks, or click blank then click option'

Astd::greater<int>

Bk

Cpop

Dstd::less<int>

Attempts:

3 left

💡 Hint

Common Mistakes

Not checking for empty input or k out of range.

Using wrong comparator or wrong method to remove elements.

Use std::greater<int> for min heap, loop until i < k, and call pop() to remove elements.

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