Kth Largest Element in an Array

Locating the kth largest element does not require establishing total order across all n items. An order-statistic pivot splits elements into those larger and smaller than itself, placing the pivot in its permanent rank. If that rank matches k, you finish immediately; otherwise, exactly one partition is discarded and the other recursed into.

Full solution

Quickselect with a random pivot: one Lomuto partition fixes the pivot at its final rank, and only the side holding index n - k is kept, giving O(n) average time in place. It beats the O(n log k) heap in an interview because it uses no extra space and never orders what it discards.

import random


def find_kth_largest(nums: list[int], k: int) -> int:
    target = len(nums) - k  # index the answer would occupy in ascending order
    lo, hi = 0, len(nums) - 1
    while True:
        # Random pivot keeps sorted or adversarial inputs off the quadratic path.
        pivot_idx = random.randint(lo, hi)
        nums[lo], nums[pivot_idx] = nums[pivot_idx], nums[lo]
        pivot = nums[lo]
        store = lo + 1  # everything before store is < pivot
        for j in range(lo + 1, hi + 1):
            if nums[j] < pivot:
                nums[store], nums[j] = nums[j], nums[store]
                store += 1
        p = store - 1
        nums[lo], nums[p] = nums[p], nums[lo]  # pivot lands at its final rank p
        if p == target:
            return nums[p]
        if p < target:
            lo = p + 1  # answer is in the larger-than-pivot side
        else:
            hi = p - 1

function findKthLargest(nums, k) {
  const target = nums.length - k; // index the answer would occupy in ascending order
  let lo = 0;
  let hi = nums.length - 1;
  while (true) {
    // Random pivot keeps sorted or adversarial inputs off the quadratic path.
    const pivotIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
    [nums[lo], nums[pivotIdx]] = [nums[pivotIdx], nums[lo]];
    const pivot = nums[lo];
    let store = lo + 1; // everything before store is < pivot
    for (let j = lo + 1; j <= hi; j++) {
      if (nums[j] < pivot) {
        [nums[store], nums[j]] = [nums[j], nums[store]];
        store++;
      }
    }
    const p = store - 1;
    [nums[lo], nums[p]] = [nums[p], nums[lo]]; // pivot lands at its final rank p
    if (p === target) return nums[p];
    if (p < target) lo = p + 1; // answer is in the larger-than-pivot side
    else hi = p - 1;
  }
}

The theory behind it

Arrays — the ground this problem stands on. All Arrays problems

What Arrays is

An array is a row of fixed boxes laid side by side in computer memory, like numbered lockers in a hallway. Because each box occupies identical space and sits directly next to its neighbors, jumping to locker zero or locker ten thousand takes the exact same tiny fraction of time. Every box holds an item of the same type, addressed by an offset number called an index.

When to reach for it

Reach for an array when items arrive in a known sequence and need immediate retrieval by position number. Problems asking for running totals, prefix accumulations, cyclic rotations, or in-place rearrangements signal array mechanics. Whenever constraints require constant-time random lookups or contiguous cache scans across fixed collections, a flat sequence is the default container.

How the pattern works

Visualize a tape with zero-indexed slots stretching from start to end. Keep track of write and read cursors when modifying contents without allocating helper buffers. For running computations, maintain an invariant such as having processed all elements left of the current index while pending elements wait to the right. When modifying entries in place, consider scanning backwards from the end so unread data is not overwritten.