Skip to main content

215. Kth Largest Element in an Array

mediumAsked at Meta

Return the k-th largest element in an unsorted array. Meta asks this to test whether you reach for a min-heap of size k or quickselect, and can articulate the n log k vs O(n) average tradeoff.

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

Source citations

Public interview reports confirming this problem appears in Meta loops.

  • Glassdoor (2026-Q1)— Meta E4 onsite reports cite this as the selection-algorithm round.
  • Blind (2025-10)— Recurring Meta interview problem.

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.

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. Sort then index

Sort descending, return index k-1.

Time
O(n log n)
Space
O(1) or O(n)
function findKthLargestSort(nums, k) {
  return nums.slice().sort((a, b) => b - a)[k - 1];
}

Tradeoff: Easiest to write — often the right answer in a phone screen. Mention this then offer the heap or quickselect.

2. Min-heap of size k

Maintain a min-heap of the k largest seen so far. New element pushes; pop the smallest when size exceeds k. Final root is the answer.

Time
O(n log k)
Space
O(k)
class MinHeap {
  constructor() { this.data = []; }
  push(v) { this.data.push(v); this._up(this.data.length - 1); }
  pop() { if (!this.data.length) return; const top = this.data[0]; const last = this.data.pop(); if (this.data.length) { this.data[0] = last; this._down(0); } return top; }
  peek() { return this.data[0]; }
  size() { return this.data.length; }
  _up(i) { while (i > 0) { const p = (i - 1) >> 1; if (this.data[p] <= this.data[i]) break; [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p; } }
  _down(i) { while (true) { const l = 2*i+1, r = 2*i+2; let best = i; if (l < this.data.length && this.data[l] < this.data[best]) best = l; if (r < this.data.length && this.data[r] < this.data[best]) best = r; if (best === i) break; [this.data[best], this.data[i]] = [this.data[i], this.data[best]]; i = best; } }
}

function findKthLargestHeap(nums, k) {
  const heap = new MinHeap();
  for (const n of nums) {
    heap.push(n);
    if (heap.size() > k) heap.pop();
  }
  return heap.peek();
}

Tradeoff: Better than sort when k << n. Heap-of-size-k is a recurring pattern (top-K problems all use it).

3. Quickselect (optimal average)

Partition like quicksort, recurse only into the side containing the target index.

Time
O(n) average, O(n^2) worst
Space
O(1) iterative
function findKthLargest(nums, k) {
  // Target index in 0-indexed ascending order:
  const target = nums.length - k;
  function partition(lo, hi) {
    const pivot = nums[hi];
    let i = lo;
    for (let j = lo; j < hi; j++) {
      if (nums[j] <= pivot) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        i++;
      }
    }
    [nums[i], nums[hi]] = [nums[hi], nums[i]];
    return i;
  }
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const p = partition(lo, hi);
    if (p === target) return nums[p];
    if (p < target) lo = p + 1;
    else hi = p - 1;
  }
  return -1;
}

Tradeoff: Average O(n) — recurse into only one side. Worst case O(n^2) on adversarial input (mitigated by randomizing the pivot). Beats heap on average but requires more careful coding.

Meta-specific tips

Meta interviewers want you to articulate three approaches and pick one based on context. State out loud: 'Sort is O(n log n). Min-heap of size k is O(n log k). Quickselect is O(n) average but O(n^2) worst.' Then pick — usually the heap for safety. Quickselect scores higher only if you implement it without bugs.

Common mistakes

  • Using a max-heap and popping k-1 times — works but is O(n log n), not the optimal k-heap approach.
  • Off-by-one in quickselect (target index for k-th LARGEST is nums.length - k in ascending order).
  • Picking quickselect under time pressure and then bugging the partition — heap is safer.

Follow-up questions

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

  • Top K Frequent Elements (LC 347).
  • K Closest Points to Origin (LC 973).
  • What if the array doesn't fit in memory? (Reservoir sampling or external sort.)

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Heap or quickselect — which does Meta prefer?

Both score equally on correctness. Heap is more defensive (no worst-case explosion); quickselect is more impressive when bug-free.

Why a min-heap for k largest?

Min-heap of size k holds the k largest; the smallest of those is at the root. When a new element exceeds the root, we know it deserves to be in the top-k and the old root drops out.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →