Skip to main content

215. Kth Largest Element in an Array

mediumAsked at DoorDash

Find the kth largest element in an unsorted array. DoorDash uses this to test heap fluency AND the average-O(n) quickselect — they want both verbally, with quickselect coded if time allows.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports cite Kth Largest as a near-default selection question.
  • Blind (2025-11)— DoorDash backend SDE reports note quickselect as the actual interview signal.

Problem

Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Can you solve it without sorting?

Constraints

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Examples

Example 1

Input
nums = [3,2,1,5,6,4], k = 2
Output
5

Example 2

Input
nums = [3,2,3,1,2,4,5,5,6], k = 4
Output
4

Approaches

1. Min-heap of size k

Maintain a min-heap of the k largest seen. The heap's root is the kth largest at the end.

Time
O(n log k)
Space
O(k)
function findKthLargest(nums, k) {
  const heap = [];
  function push(v) {
    heap.push(v);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p] > heap[i]) { [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; }
      else break;
    }
  }
  function pop() {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2*i+1, r = 2*i+2;
        let small = i;
        if (l < heap.length && heap[l] < heap[small]) small = l;
        if (r < heap.length && heap[r] < heap[small]) small = r;
        if (small === i) break;
        [heap[i], heap[small]] = [heap[small], heap[i]];
        i = small;
      }
    }
    return top;
  }
  for (const num of nums) {
    push(num);
    if (heap.length > k) pop();
  }
  return heap[0];
}

Tradeoff: Easier to reason about than quickselect. O(n log k) is fast enough for n = 10^5. Default to this in interviews unless asked for the O(n) average.

2. Quickselect (Hoare partition)

Like quicksort but only recurse on the side containing the answer. Average O(n), worst O(n^2). Randomize pivot to expect average behavior.

Time
O(n) avg / O(n^2) worst
Space
O(1)
function findKthLargestQuickselect(nums, k) {
  const target = nums.length - k;
  function partition(l, r) {
    const pivot = nums[r];
    let i = l;
    for (let j = l; j < r; j++) {
      if (nums[j] <= pivot) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        i++;
      }
    }
    [nums[i], nums[r]] = [nums[r], nums[i]];
    return i;
  }
  function select(l, r) {
    while (l < r) {
      const swap = l + Math.floor(Math.random() * (r - l + 1));
      [nums[swap], nums[r]] = [nums[r], nums[swap]];
      const p = partition(l, r);
      if (p === target) return nums[p];
      if (p < target) l = p + 1;
      else r = p - 1;
    }
    return nums[l];
  }
  return select(0, nums.length - 1);
}

Tradeoff: Average O(n) with random pivot. Bloomberg interviewers grade for naming this. Worst case O(n^2) — mention the randomization step out loud.

DoorDash-specific tips

DoorDash interviewers want BOTH solutions verbally. Lead with min-heap (cleaner under pressure), then state: 'I could also use quickselect for average O(n).' If asked to code, do quickselect — that's the harder signal.

Common mistakes

  • Confusing kth largest with kth smallest (use nums.length - k as the target index after sorting).
  • Forgetting the random pivot in quickselect — adversarial input makes it O(n^2).
  • Using sort — O(n log n), works but doesn't show breadth.

Follow-up questions

An interviewer at DoorDash may pivot to one of these next:

  • Wiggle Sort II (LC 324) — needs the median (kth largest, k = n/2).
  • Top K Frequent Elements (LC 347) — same heap or bucket sort.
  • K Closest Points to Origin (LC 973) — heap variant.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is quickselect average O(n)?

Each partition halves the search range on average, giving n + n/2 + n/4 + ... = O(n).

Heap or quickselect?

Heap is more predictable. Quickselect can hit O(n^2) on pathological input without random pivot. In interview, default to heap; mention quickselect as the average-faster alternative.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Kth Largest Element in an Array and other DoorDash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →