Kth Largest Element

Hints

1. Reflex answer. Sort descending and return the element at index k − 1. O(n log n), works, doesn't earn the question.
2. K-th largest is the same as (n − k)-th smallest. Either direction works; pick whichever simplifies the implementation.
3. Heap-of-K. Maintain a min-heap of size K. After processing every element, the heap contains the K largest, with the K-th largest at the root. O(n log k); beats sort when K is small.
4. Quickselect. Partition like quicksort, but only recurse into the half containing the K-th element. Expected O(n) with random pivot.
5. Worst case of quickselect. Pathological pivots make it O(n²). Randomise the pivot to make this extremely unlikely; median-of-medians for deterministic O(n) (rarely worth it).
6. Standard library shortcut. C++ has std::nth_element; Python's heapq.nlargest(k, nums)[-1] works but is O(n log k). For interviews, implement quickselect.

Solution, three approaches

Approach 1 · Sort. O(n log n) time, O(1) space

def find_kth_largest_sort(nums, k):
    nums.sort()
    return nums[-k]                                  # K-th from the end

One line, correct, easy to read. The interviewer expects you to write it and then improve.

Approach 2 · Heap of size K, O(n log k) time, O(k) space

Maintain a min-heap with at most K elements. For each new element, push; if the heap exceeds size K, pop the smallest. After processing every element, the heap contains the K largest, with the K-th largest at the root.

import heapq

def find_kth_largest_heap(nums, k):
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)
    return heap[0]

Each push/replace is O(log k). Total: O(n log k). Beats sort when K is much smaller than n, which is the common case in interview problems. Also works for streams: process each element on arrival, never see the whole array at once.

Approach 3 · Quickselect. O(n) expected, O(1) space

Quicksort's partition without the recursion into the other half. Each partition is O(n); the recursion shrinks the problem by an expected factor of 3/4 per round, so total work is O(n) expected.

import random

def find_kth_largest(nums, k):
    target = len(nums) - k                          # 0-indexed position of the K-th largest
    lo, hi = 0, len(nums) - 1
    while True:
        # Random pivot avoids pathological O(n²).
        p = random.randint(lo, hi)
        nums[p], nums[hi] = nums[hi], nums[p]
        pivot_idx = partition(nums, lo, hi)
        if pivot_idx == target:
            return nums[pivot_idx]
        elif pivot_idx < target:
            lo = pivot_idx + 1
        else:
            hi = pivot_idx - 1

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

Why random pivot: a fixed "always last element" pivot is O(n²) on already-sorted or reverse-sorted input. Randomising makes adversarial inputs cost O(n) in expectation; the variance is bounded.

Why we iterate (no recursion): quickselect only ever descends into one of the two halves. The recursive form wastes stack frames for nothing; the iterative form is O(1) extra memory.

Complexity comparison

Edge cases to verify

• k = 1. Returns the maximum. All three approaches handle this trivially.
• k = n. Returns the minimum.
• Array with duplicates. Two-way partition can produce unbalanced halves; consider three-way partition (Dutch flag) for duplicate-heavy inputs.
• Single-element array. Quickselect's loop terminates immediately when lo == hi.
• All elements equal. Two-way partition becomes O(n²) worst case. Three-way partition stays O(n).

Where beginners go wrong

• Fixed pivot. Always-last-element pivot is O(n²) on sorted or reverse-sorted input. Random pivot is the simplest fix.
• Recursing into both halves. That's quicksort. Quickselect descends only into the half containing the K-th position.
• Off-by-one on the target index. K-th largest at 1-indexed position k becomes 0-indexed position n − k. Mixing conventions causes silent wrong answers.
• Heap-of-K with a max-heap. A max-heap of n elements then K pops is O(n log n + k log n), slower than sort. The trick is a min-heap capped at K: push everything, pop on overflow; the root is the K-th largest.
• Modifying the array when the caller didn't expect it. Quickselect rearranges its input. Document this or copy first.

Interview follow-ups to expect

• "Return the top K, not just the K-th." Quickselect for the K-th, then everything to its right is the top K (unsorted). One more partition or sort the K-element suffix if order matters.
• "K-th smallest pair distance." Binary search on the distance plus a feasibility check, see Binary Search on the Answer.
• "Stream of integers, return the K-th largest at any moment." Heap-of-K, updated incrementally. Each insert is O(log k).
• "Find K closest points to origin." Same shape, quickselect by distance² or heap-of-K.
• "Median of a stream." Two heaps, see Heap as Array Arithmetic.

Related reading

• Quickselect (K-th in Linear Time) the deep-dive on the partition-and-descend pattern.
• Heap as Array Arithmetic, the underpinning of the heap-of-K alternative.
• Sorting & Search, the module that frames sorting as preparation rather than the goal.