Kth Smallest and Largest Using Heap: DSA Guide

Two tools, one job. Heap: safe and streaming-friendly. Quickselect: fastest on average, but mutates the array.

“Kth largest/smallest” → size-k heap (safe) or quickselect (fast)

Pattern 1: Min-Heap of Size k

Same trick as top-k: the root ends up being exactly the answer.

public int kthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int x : nums) {
        heap.offer(x);
        if (heap.size() > k) heap.poll();
    }
    return heap.peek();
}

import heapq

def kth_largest(nums, k):
    return heapq.nlargest(k, nums)[-1]
    # or manual: keep heap size k, return heap[0]

int kthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int x : nums) {
        heap.push(x);
        if ((int)heap.size() > k) heap.pop();
    }
    return heap.top();
}

function kthLargest(nums, k) {
  const heap = new MinHeap();
  for (const x of nums) {
    heap.push(x);
    if (heap.size() > k) heap.pop();
  }
  return heap.peek();
}

Kth smallest? Flip the comparison: max-heap of size k, evict when larger than root.

Pattern 2: Quickselect

Heap keeps the best two; quickselect throws away half the array per round. Press ▶.

Kth Smallest — Max-Heap of Size k

Flip the comparison: use a MAX-heap of size k. The root is the largest of the k smallest elements — exactly the kth smallest. When a new element is smaller than the root, evict the root and insert the new one.

Array: [3,2,1,5,6,4], k=2. We build a max-heap of size 2. Once full, each new element smaller than the root evicts it. After one pass, the root is the 2nd smallest. Same O(n log k) as kth largest — just flip '>' to '<'.

HEAP VISUALIZER

Steps –

ARRAY BACKING

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        heap = max-heap, size k
                      
                        2
                        for x in nums:
                      
                        3
                          if size < k: push(x)
                      
                        4
                          elif x < root:
                      
                        5
                            pop(); push(x)      # keep best k smallest
                      
                        6
                        # kth smallest == root

Quicksort’s partition, but only recurse into ONE side — the side that contains index n−k:

public int kthLargest(int[] a, int k) {
    return select(a, 0, a.length - 1, a.length - k);
}

int select(int[] a, int lo, int hi, int target) {
    int p = partition(a, lo, hi);
    if (p == target) return a[p];
    return p < target
        ? select(a, p + 1, hi, target)
        : select(a, lo, p - 1, target);
}

int partition(int[] a, int lo, int hi) {
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) swap(a, i++, j);
    swap(a, i, hi);
    return i;
}

import random

def kth_largest(nums, k):
    def select(lo, hi, t):
        p = random.randint(lo, hi)
        nums[p], nums[hi] = nums[hi], nums[p]
        pivot, i = nums[hi], lo
        for j in range(lo, hi):
            if nums[j] < pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[hi] = nums[hi], nums[i]
        if i == t:   return nums[i]
        if i < t:    return select(i + 1, hi, t)
        return select(lo, i - 1, t)

    return select(0, len(nums) - 1, len(nums) - k)

int kthLargest(vector<int>& a, int k) {
    nth_element(a.begin(), a.begin() + k - 1, a.end(),
                greater<int>());
    return a[k - 1];
    // or hand-rolled quickselect like the Java version
}

function kthLargest(nums, k) {
  const target = nums.length - k;
  let lo = 0,
    hi = nums.length - 1;
  for (;;) {
    const p = partition(nums, lo, hi);
    if (p === target) return nums[p];
    if (p < target) lo = p + 1;
    else hi = p - 1;
  }
}

function partition(a, lo, hi) {
  const pivot = a[hi];
  let i = lo;
  for (let j = lo; j < hi; j++)
    if (a[j] < pivot) [a[i], a[j]] = [a[j--], 0]; // see note
  return i;
}

JS note: write the swap properly — [a[i], a[j]] = [a[j], a[i]]; i++;

Randomize the pivot. Sorted input with a fixed last-element pivot degrades to O(n²).

Quickselect halves expected work by never touching the wrong half — average O(n), worst O(n²).

Common Mistakes

Confusing k-th largest index: ascending position is n − k, not k.
No random pivot → TLE on adversarial/sorted tests.
Recursing into BOTH sides after partition (that’s full quicksort).
Off-by-one in the partition loop (j < hi, not j <= hi).

Complexity

Approach	Average	Worst	Space
Sort	O(n log n)	O(n log n)	O(1)+
Size-k heap	O(n log k)	O(n log k)	O(k)
Quickselect	O(n)	O(n²)	O(1) in-place

⚠️ Animation & Content Notice

Kth Smallest & Largest

Pattern 1: Min-Heap of Size k

Pattern 2: Quickselect

⚠️ Animation & Content Notice

Kth Smallest — Max-Heap of Size k

Common Mistakes

Complexity

Premium Content

My Private Notes

Earn Premium with Referrals

Pattern 1: Min-Heap of Size k

Pattern 2: Quickselect

Kth Smallest — Max-Heap of Size k

Common Mistakes

Complexity

Premium Content

My Private Notes