Kth Largest Element in an Array: Heap and Quickselect

The Problem

You are given an unsorted array of integers and an integer k. Return the kth largest element. This means kth largest in sorted order, not the kth distinct value, so duplicates count separately.

Example 1

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Why: sorted descending, the array is 6, 5, 4, 3, 2, 1, and the second value is 5.

Example 2

Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4
Why: sorted descending: 6, 5, 5, 4, ... The two 5s both count.

Assumptions to confirm

• Is k always between 1 and the array length? (Assume yes.)
• Do duplicates count separately? (Yes.)
• Can you modify the input array? (It affects whether quickselect can work in place.)

Start With the Brute Force

The simplest answer sorts the array and returns the element at index n - k. That is O(n log n) time and perfectly acceptable as a first answer, and in many real codebases it is the right one.

The interviewer then asks whether you can avoid sorting everything. You only need the top k values, or even just one position in sorted order, so a full sort does more work than necessary.

The Optimal Approach: A Min-Heap of Size k

Solution in Python and TypeScript

Python has a min-heap built in (heapq). TypeScript does not, so the TypeScript version includes a short heap class; in an interview, ask whether you may assume one exists.

Python

import heapq
import random


def find_kth_largest(nums: list[int], k: int) -> int:
    heap: list[int] = []  # min-heap of the k largest seen so far
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)  # drop the smallest
    return heap[0]


def find_kth_largest_quickselect(nums: list[int], k: int) -> int:
    target = len(nums) - k  # index of the answer in sorted order
    arr = nums[:]
    lo, hi = 0, len(arr) - 1
    while True:
        pivot = arr[random.randint(lo, hi)]
        less = [x for x in arr[lo:hi + 1] if x < pivot]
        equal = [x for x in arr[lo:hi + 1] if x == pivot]
        more = [x for x in arr[lo:hi + 1] if x > pivot]
        arr[lo:hi + 1] = less + equal + more
        if target < lo + len(less):
            hi = lo + len(less) - 1
        elif target < lo + len(less) + len(equal):
            return pivot
        else:
            lo = lo + len(less) + len(equal)

TypeScript

// TypeScript has no built-in heap, so this is a small min-heap.
class MinHeap {
  private data: number[] = [];
  get size(): number { return this.data.length; }
  peek(): number { return this.data[0]; }
  push(value: number): void {
    const d = this.data;
    d.push(value);
    let i = d.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (d[parent] <= d[i]) break;
      [d[parent], d[i]] = [d[i], d[parent]];
      i = parent;
    }
  }
  pop(): number {
    const d = this.data;
    const top = d[0];
    const last = d.pop()!;
    if (d.length > 0) {
      d[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1;
        const r = l + 1;
        let smallest = i;
        if (l < d.length && d[l] < d[smallest]) smallest = l;
        if (r < d.length && d[r] < d[smallest]) smallest = r;
        if (smallest === i) break;
        [d[smallest], d[i]] = [d[i], d[smallest]];
        i = smallest;
      }
    }
    return top;
  }
}

function findKthLargest(nums: number[], k: number): number {
  const heap = new MinHeap(); // the k largest seen so far
  for (const num of nums) {
    heap.push(num);
    if (heap.size > k) heap.pop(); // drop the smallest
  }
  return heap.peek();
}

The Python file also includes quickselect, the O(n) average answer. It picks a random pivot, splits the values into smaller, equal and larger groups, and keeps only the group that contains the target position. In an interview it is usually enough to explain quickselect and code the heap, unless you are asked for both.

For a deeper look at heaps themselves, see heapify and building a max heap.

Time and Space Complexity

How to Talk Through Kth Largest Element in an Interview

1. Clarify: "Kth largest by sorted position, so duplicates count? Can I modify the array?"
2. Brute force: "Sorting gives it in O(n log n), but I only need part of the order."
3. Optimise: "A min-heap holding the k largest so far keeps the answer at the top, so it is O(n log k). Quickselect gets O(n) on average by recursing into one side only."
4. Code: narrate why you pop when the heap exceeds k.
5. Test: the two examples, k = 1, and k = n. State the complexity of the version you wrote.

Edge Cases and Common Follow-Ups

Practise Kth Largest Element in a Mock Coding Round

Reading a solution is not the same as producing one with someone listening. The gap shows up as long silences, a jump straight to code without a brute force, or a bug you only spot after the interviewer asks you to test. The fix is to rehearse problems like Kth Largest Element out loud, under time pressure, while explaining each decision.

MockIF runs mock coding interviews with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, adds follow-up questions the way a real interviewer would, and then scores your answer and gives specific feedback. Each session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing).

Frequently Asked Questions