DSA problem
Kth Largest Element in an Array
Given an integer array nums and an integer k, return the k-th largest element in the array. Note that it is the k-th largest element in the sorted order, not the k-th distinct element. Can you solve it without sorting?
The simplest correct solution is to sort the array in ascending order and return nums[n - k], which costs O(n log n) time. A popular alternative uses a min-heap of size k: iterate through the array, push each value, and pop the smallest whenever the heap exceeds size k; at the end the root is the answer. The heap approach runs in O(n log k) time and O(k) extra space — strictly better than sorting when k is small relative to n.
The canonical optimal approach, however, is Quickselect — a partition-based selection algorithm derived from QuickSort. The k-th largest element occupies index n - k in the ascending-sorted array. Quickselect locates that index without fully sorting: it partitions the array around a chosen pivot, then recurses (or iterates) only into the side of the partition that contains the target index. Each level of recursion does O(n) work on a region of shrinking expected size, so the expected total work is O(n + n/2 + n/4 + ...) = O(n).
To avoid the pathological O(n^2) worst case on adversarial inputs (already-sorted arrays, all-equal arrays), we randomize the pivot by picking a random index in the current range and swapping it into the partition slot before running the Lomuto (or Hoare) partition. With a random pivot the expected time complexity is O(n), with O(1) extra space when implemented iteratively (and O(log n) average recursion depth when implemented recursively). The worst case is still O(n^2) but is vanishingly unlikely for any specific input.
Examples
nums = [3,2,1,5,6,4], k = 25nums = [3,2,3,1,2,4,5,5,6], k = 44nums = [1], k = 11Constraints
- 1 <= k <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- You should aim for an algorithm better than O(n log n) sorting.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.