Kth Smallest

JavaView on GFG

Problem Overview

Find kth smallest element in unsorted array.

See our study guide for structured GFG and LeetCode practice.

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?