Kth Smallest

JavaView on GFG

Intuition

Find kth smallest element in unsorted array. Quickselect or min-heap.

Algorithm

1Quickselect: partition around pivot. If pivot index == k-1: return. Else recurse left or right.

Common Pitfalls

•Quickselect O(n) average, O(n^2) worst. For guaranteed O(n log k): use max-heap of size k.

Kth Smallest.java

Java

// Approach: Min-heap merge of k sorted arrays, or binary search on value with counting.
// Time: O(k log n) Space: O(n)
import java.util.*;

class Solution {
    public static int kthSmallest(int[] arr, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

        for (int val : arr) {
            pq.offer(val);

            if (pq.size() > k)
                pq.poll();
        }

        return pq.poll();
    }
}

Was this solution helpful?