Skip to main content

215. Kth Largest Element in an Array

mediumAsked at Snap

Snap's notification ranking surfaces the top-K most-engaged snaps in a user's inbox — finding the Kth largest is the primitive that backs that ranking without a full sort.

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

Problem

Given an integer array nums and an integer k, return the kth largest element in the array. This is the kth largest in 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. Min-heap of size k

Maintain a min-heap of size k. For each element: push onto heap, then pop if size exceeds k. After the full pass, the heap's minimum is the kth largest. Uses O(k) space — valuable when k << n.

Time
O(n log k)
Space
O(k)
class MinHeap {
  constructor() { this.data = []; }
  push(val) {
    this.data.push(val);
    this._bubbleUp(this.data.length - 1);
  }
  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) { this.data[0] = last; this._sinkDown(0); }
    return top;
  }
  peek() { return this.data[0]; }
  size() { return this.data.length; }
  _bubbleUp(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;
    }
  }
  _sinkDown(i) {
    const n = this.data.length;
    while (true) {
      let min = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.data[l] < this.data[min]) min = l;
      if (r < n && this.data[r] < this.data[min]) min = r;
      if (min === i) break;
      [this.data[min], this.data[i]] = [this.data[i], this.data[min]];
      i = min;
    }
  }
}
function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const num of nums) {
    heap.push(num);
    if (heap.size() > k) heap.pop();
  }
  return heap.peek();
}

Tradeoff:

2. Quickselect (average O(n))

Partition around a pivot like QuickSort, but only recurse into the side that contains the kth position. Average O(n), worst O(n^2) — acceptable for interviews but min-heap is safer when distribution is adversarial.

Time
O(n) average, O(n^2) worst
Space
O(1)
function findKthLargest(nums, k) {
  const target = nums.length - k; // kth largest = target-th smallest (0-indexed)
  function partition(lo, hi) {
    const pivot = nums[hi];
    let store = lo;
    for (let i = lo; i < hi; i++) {
      if (nums[i] <= pivot) {
        [nums[store], nums[i]] = [nums[i], nums[store]];
        store++;
      }
    }
    [nums[store], nums[hi]] = [nums[hi], nums[store]];
    return store;
  }
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const pi = partition(lo, hi);
    if (pi === target) return nums[pi];
    if (pi < target) lo = pi + 1;
    else hi = pi - 1;
  }
}

Tradeoff:

Snap-specific tips

Snap notification infra ranks snaps by engagement score in real time. The interviewer will ask 'what if the array is streaming in and k is very large?' — answer with a max-heap of the full array for one-shot, or a count-min sketch for unbounded streams.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →