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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Extraction

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

DSA Java

import java.util.PriorityQueue;

public class KthSmallest {
    public static int findKthSmallest(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : arr) {
            minHeap.add(num);
        }
        int result = -1;
        for (int i = 0; i < k; i++) {
            result = minHeap.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] array = {7, 10, 4, 3, 20, 15};
        int k = 3;
        System.out.println(findKthSmallest(array, k));
    }
}

A 7

B 4

C 10

D 3

💡 Hint

Remember that the min heap always removes the smallest element first.

The min heap orders elements from smallest to largest. Polling three times removes 3, then 4, then 7. So the 3rd smallest element is 7.

🧠 Conceptual

intermediate

Understanding Min Heap Behavior

Which statement correctly describes the behavior of a min heap when used to find the kth smallest element?

A Polling the min heap k times returns the kth smallest element.

B The min heap removes the largest element first when polling.

C The min heap stores elements in descending order internally.

D Adding elements to a min heap sorts them in place.

💡 Hint

Think about what 'min' means in min heap.

A min heap always keeps the smallest element at the top. Polling removes the smallest element each time, so after k polls, you get the kth smallest element.

🔧 Debug

advanced

Identify the Error in Kth Smallest Element Code

What error will occur when running this code to find the 5th smallest element?

DSA Java

import java.util.PriorityQueue;

public class KthSmallest {
    public static int findKthSmallest(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : arr) {
            minHeap.add(num);
        }
        int result = -1;
        for (int i = 0; i <= k; i++) {
            result = minHeap.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] array = {5, 3, 8, 6, 2};
        int k = 5;
        System.out.println(findKthSmallest(array, k));
    }
}

A Output is 8

B No error, output is 6

C NullPointerException

D IndexOutOfBoundsException

💡 Hint

Check the loop condition and how many times poll() is called.

The loop runs k+1 times (6 times for k=5) but the heap only has 5 elements. The last poll returns null, causing a NullPointerException when unboxing to int.

🚀 Application

advanced

Resulting Heap State After Insertions

After inserting the elements [12, 3, 5, 7, 19] into an empty min heap, what is the state of the heap array (level order)?

A [5, 3, 7, 12, 19]

B [3, 7, 5, 12, 19]

C [3, 5, 12, 7, 19]

D [3, 5, 7, 12, 19]

💡 Hint

Min heap keeps the smallest element at the root and maintains heap property after each insertion.

Inserting elements one by one and heapifying results in [3, 5, 7, 12, 19] as the level order array representation of the min heap.

❓ Predict Output

expert

Output of Kth Smallest Element with Duplicate Values

What is the output of the following Java code that finds the 5th smallest element in an array with duplicates using a min heap?

DSA Java

import java.util.PriorityQueue;

public class KthSmallest {
    public static int findKthSmallest(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : arr) {
            minHeap.add(num);
        }
        int result = -1;
        for (int i = 0; i < k; i++) {
            result = minHeap.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] array = {2, 3, 3, 1, 4, 2, 5};
        int k = 5;
        System.out.println(findKthSmallest(array, k));
    }
}

A 4

B 3

C 2

D 5

💡 Hint

Duplicates are counted separately when polling from the min heap.

The sorted array with duplicates is [1, 2, 2, 3, 3, 4, 5]. Polling five times removes 1, 2, 2, 3, 3. So the 5th smallest element is 3.

Practice

1. What does the kth smallest element mean in a list of numbers?

easy

A. The element that is the kth in ascending order

B. The largest element in the list

C. The element that appears kth from the end

D. The element with the kth highest frequency

Solution

1. Step 1: Understand the meaning of kth smallest

   The kth smallest element is the element that would appear at position k if the list was sorted in ascending order.

2. Step 2: Compare with other options

   Options B, C, and D describe different concepts: largest element, kth from end, and frequency-based element, which are not the kth smallest.

3. Final Answer:

   The element that is the kth in ascending order -> Option A

4. Quick Check:

   kth smallest = kth element in sorted list [OK]

Hint: Sort the list; kth smallest is element at index k-1 [OK]

Common Mistakes:

• Confusing kth smallest with kth largest
• Thinking kth smallest means kth from the end
• Mixing element frequency with position

2. Which Java code snippet correctly creates a min heap using PriorityQueue to find the kth smallest element?

easy

A. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.reverseOrder());

B. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder());

C. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder(), k);

D. PriorityQueue<Integer> minHeap = new PriorityQueue<>();

Solution

1. Step 1: Identify min heap creation syntax

   In Java, new PriorityQueue<>() creates a min heap by default.

2. Step 2: Analyze other options

   Options B, C, and D create max heaps using reverse order comparators.

3. Final Answer:

   PriorityQueue<Integer> minHeap = new PriorityQueue<>(); -> Option D

4. Quick Check:

   Default PriorityQueue = min heap [OK]

Hint: Use PriorityQueue without comparator for min heap [OK]

Common Mistakes:

• Using reverseOrder() creates max heap, not min heap
• Confusing initial capacity with heap type
• Not importing java.util.PriorityQueue

3. What is the output of the following Java code snippet?

int[] arr = {7, 10, 4, 3, 20, 15};
int k = 3;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : arr) {
    minHeap.add(num);
}
int result = 0;
for (int i = 0; i < k; i++) {
    result = minHeap.poll();
}
System.out.println(result);

medium

A. 10

B. 4

C. 7

D. 3

Solution

1. Step 1: Add all elements to min heap

   Elements added: 7, 10, 4, 3, 20, 15. Min heap orders them internally as 3,4,7,10,15,20.

2. Step 2: Poll k=3 times from min heap

   First poll: 3, second poll: 4, third poll: 7. The variable result holds the last polled value, 7.

3. Final Answer:

   7 -> Option C

4. Quick Check:

   3rd smallest element = 7 [OK]

Hint: Poll k times from min heap; last polled is kth smallest [OK]

Common Mistakes:

• Returning first polled element instead of kth
• Confusing min heap order with insertion order
• Off-by-one error in loop count

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

int kthSmallest(int[] arr, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int i = 0; i <= arr.length; i++) {
        minHeap.add(arr[i]);
    }
    int result = 0;
    for (int i = 0; i < k; i++) {
        result = minHeap.poll();
    }
    return result;
}

medium

A. Loop condition should be i < arr.length, not i <= arr.length

B. PriorityQueue should be max heap, not min heap

C. Poll loop should run k+1 times

D. Return statement should return minHeap.peek()

Solution

1. Step 1: Check array loop bounds

   The for loop uses i <= arr.length, which causes ArrayIndexOutOfBoundsException because valid indices are 0 to arr.length-1.

2. Step 2: Verify other parts

   Min heap is correct for kth smallest. Poll loop runs k times correctly. Return statement returns last polled element, which is correct.

3. Final Answer:

   Loop condition should be i < arr.length, not i <= arr.length -> Option A

4. Quick Check:

   Array index out of bounds due to loop condition [OK]

Hint: Use i < arr.length to avoid index errors [OK]

Common Mistakes:

• Using <= instead of < in array loops
• Changing heap type unnecessarily
• Polling wrong number of times

5. Given a large array with millions of elements, which approach is most efficient to find the kth smallest element?

hard

A. Add all elements to a min heap and poll k times

B. Add first k elements to a max heap, then for each remaining element, replace root if smaller

C. Sort the entire array and pick element at index k-1

D. Use a hash map to count frequencies and pick kth smallest key

Solution

1. Step 1: Understand efficiency of adding all elements to min heap

   Adding all millions of elements to a min heap and polling k times is O(n + k log n), which is costly for large n.

2. Step 2: Use max heap of size k for better efficiency

   Adding first k elements to a max heap keeps track of k smallest seen so far. For each new element, if smaller than max heap root, replace root. This is O(n log k), much better for large n.

3. Step 3: Compare other options

   Sorting entire array is O(n log n), slower than max heap approach. Hash map frequency counting is not suitable for kth smallest element.

4. Final Answer:

   Add first k elements to a max heap, then for each remaining element, replace root if smaller -> Option B

5. Quick Check:

   Max heap of size k = efficient kth smallest [OK]

Hint: Use max heap of size k for large arrays [OK]

Common Mistakes:

• Using min heap with all elements for large data
• Sorting entire array unnecessarily
• Confusing frequency counting with order statistics