Kth Largest Element in an Array

The k-th largest value is defined by the sorted order, so produce that order. Sorted from largest to smallest, [7, 2, 9, 4, 9, 1] becomes [9, 9, 7, 4, 2, 1], and the k-th largest sits at index k-1. For k = 2 that is index 1, the second 9. If your sort puts the smallest first, read index n-k instead: index 4 of [1, 2, 4, 7, 9, 9] is the same 9.

Duplicates need no special handling: a sort keeps every copy, and every copy takes its own position.

With n = 10^4 a sort makes about n log n ≈ 1.3 × 10^5 comparisons, which passes every test. The waste is that it puts all n values in order when only one position matters. The next two approaches do less of that work.

The k-th largest value is the smallest of the k largest values. So walk through nums once and keep only the k largest values seen so far, in a min-heap. The top of a min-heap is its smallest value, which is exactly the candidate answer.

When a value x arrives and the heap holds fewer than k values, add it. Otherwise compare x with the top. If x is not larger, at least k values you kept are as large as x, so x can never be the answer and you skip it. If x is larger, the top has dropped out of the k largest: replace it with x. In example 2 with k = 4, the first four values fill the heap with 5, -3, 8, 0 and the top is -3. Then 2 beats -3 and replaces it, the top becomes 0, and 0 is the answer.

Every value costs at most one heap operation of O(log k), so the total is O(n log k) time and O(k) memory. That beats sorting when k is small, and it works on a stream: you never need all the values at once. Python has heapq, Java PriorityQueue, C++ priority_queue with greater, Go container/heap, Rust BinaryHeap with Reverse and PHP SplMinHeap. The code for the other languages writes the heap in an array, where the children of index i sit at 2i+1 and 2i+2, or at 2i and 2i+1 in Lua and R, which count from 1.

Quicksort picks a pivot and partitions: smaller values to its left, larger values to its right. After one partition the pivot sits at its final sorted index, even though neither side is sorted yet. Quickselect uses that fact. In smallest-first order the answer lives at index target = n-k. After a partition, target is either left of the pivot, at the pivot, or right of it, so you continue on one side and drop the other.

For [7, 2, 9, 4, 9, 1] and k = 2, target is 6-2 = 4. Partition around 4: 2 and 1 take indexes 0 and 1, 4 takes index 2, and 7, 9, 9 take indexes 3 to 5. Index 4 is to the right, so you keep only indexes 3 to 5. Partition those around 9: 7 takes index 3 and both 9s take indexes 4 and 5. Index 4 holds a 9, so the answer is 9.

Use a three-way partition: values below the pivot, then values equal to it, then values above it, tracked by lt and gt. The equal block [lt, gt] is in its sorted place, so if target falls inside it you are done. With a plain two-way partition, an array of 10^4 copies of 7 shrinks by one value per round, about 5 × 10^7 steps; the three-way version answers it in one pass.

Pick the pivot at random. Half the time it lands in the middle half of the range, which cuts the range to at most three quarters, so the expected work is a few passes over n values: O(n). The worst case is still O(n²) if every pivot is an extreme value, and a fixed choice such as the first element hits it on sorted input. The code works on a copy, which costs O(n) memory; partitioning nums itself brings that to O(1) if you may change the input.