The problem
Given an integer array nums and a number k, return the k-th largest element — the one that would be k-th from the end if the array were sorted, so repeats count. Try to do it without sorting.
Examples
- Input
nums = [3, 2, 1, 5, 6, 4], k = 2
- Output
5
- Input
nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
- Output
4
Constraints
- 1 ≤ k ≤ nums.length ≤ 10⁵
- −10⁴ ≤ nums[i] ≤ 10⁴
The idea
The k-th largest is the element that would sit at position n − k in sorted order. Quickselect finds it without sorting the rest: pick a pivot value and partition the array into three blocks — smaller than the pivot, equal to it, larger than it.
Now only one block can hold position n − k: if it falls in the equal block, the pivot is the answer; otherwise repeat inside the block that holds it, and ignore the other two. Each round keeps, on average, about half, so the work is n + n/2 + n/4 + … ≈ 2n. Choosing the pivot at random means no input can make every choice bad; the three-way split keeps runs of equal values from slowing it down.
- Time
- O(n) on average; O(n²) in the worst case, which a random pivot makes vanishingly rare
- Space
- O(1) — partitions in place
Solution · every language run against every case
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: # Quickselect: the k-th largest is the one that would sit at index n - k if sorted. target = len(nums) - k lo, hi = 0, len(nums) - 1 while True: pivot = nums[random.randint(lo, hi)] # a random pivot defeats adversarial inputs # Three-way partition of lo..hi: < pivot, then == pivot, then > pivot. lt, i, gt = lo, lo, hi while i <= gt: if nums[i] < pivot: nums[lt], nums[i] = nums[i], nums[lt] lt += 1 i += 1 elif nums[i] > pivot: nums[gt], nums[i] = nums[i], nums[gt] gt -= 1 else: i += 1 if target < lt: hi = lt - 1 # it is among the smaller ones elif target > gt: lo = gt + 1 # among the larger ones else: return pivot # it lands in the block equal to the pivot