Skip to main content
Sorting Tricks

Kth Element (QuickSelect)

Find the Kth smallest element in expected O(n) without fully sorting. Partition like quicksort. If the pivot lands at position K, done. If K is in the left partition, recurse left only. Recurse into only ONE side.

O(n) average
·
O(1)

How It Works

QuickSelect finds the kth smallest element without fully sorting. Partition the array around a pivot exactly as in quick sort; the pivot lands at its final sorted index p. If p equals k, done. If k is smaller, the answer lies entirely in the left segment, so recurse only there; otherwise recurse only right. Discarding one side each round is the whole trick.

With random pivots, expected work forms a geometric series — n + n/2 + n/4 + ... — summing to O(n) expected time and O(1) space with iterative partitioning, versus O(n log n) for sorting or O(n log k) for a size-k heap. The worst case is O(n^2) with adversarially bad pivots; the median-of-medians pivot rule guarantees O(n) deterministically but with constants that make it rare in practice. QuickSelect mutates the array, which is its main practical caveat.

Step-by-Step Visualization

Find 2nd largest in [3,2,1,5,6,4] → k=4 (0-indexed)
3
0
2
1
1
2
5
3
6
4
4
5
K2nd largest = index 4
1/4

Code

Java
static int findKthLargest(int[] nums, int k) {
  k = nums.length - k; // Convert to kth smallest

  return quickSelect(nums, k, 0, nums.length - 1);
}

static int quickSelect(int[] nums, int k, int lo, int hi) {
  int pivot = nums[hi];
  int i = lo;
  for (int j = lo; j < hi; j++) {
    if (nums[j] <= pivot) {
      int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
      i++;
    }
  }
  int tmp = nums[i]; nums[i] = nums[hi]; nums[hi] = tmp;
  if (i == k) return nums[i];
  return i < k ? quickSelect(nums, k, i + 1, hi) : quickSelect(nums, k, lo, i - 1);
}

Tips & Gotchas

1QuickSelect is like quicksort but only recurses into one half
2Partition around a pivot, check which side the kth element falls
3Average O(n) but worst case O(n²) — use random pivot to avoid

Practice Problems

  • 1Kth Largest Element in an Array
  • 2K Closest Points to Origin
  • 3Top K Frequent Elements
  • 4Find the Kth Largest Integer in the Array

About the Sorting Tricks Pattern

Patterns where sorting is used as a tool to solve a different problem.

Key insight

Sorting unlocks binary search, two-pointer, and greedy. Always ask: can I sort first? Custom comparators solve tricky ordering problems. Know QuickSelect for O(n) expected Kth element.

Common Sorting Interview Problems

  • Sort Colors
  • Kth Largest Element
  • Merge Intervals
  • Largest Number
  • Sort List
  • Meeting Rooms

Frequently Asked Questions

Why is QuickSelect O(n) on average when quick sort is O(n log n)?

Quick sort recurses into both partitions, paying O(n) at every one of log n levels. QuickSelect keeps only the side containing index k, so the expected subproblem size halves each round; the resulting series n + n/2 + n/4 + ... converges to 2n, hence linear expected time.

When should I prefer a heap over QuickSelect for a top-k problem?

Use a size-k heap when the data arrives as a stream, when the input must not be mutated, or when a hard O(n log k) worst-case bound is required. QuickSelect wins on expected speed and space for a static in-memory array where reordering is acceptable.

How do I find the kth largest rather than kth smallest?

Either select index n-k in ascending order — kth largest and (n-k+1)th smallest are the same element — or flip the partition comparison to arrange larger elements first and select index k-1. The index translation approach avoids touching the partition logic and is less error-prone.