Skip to main content

22. Kth Largest Element in an Array

mediumAsked at Yelp

Find the kth largest element in an unsorted array — Yelp uses min-heap-of-size-k to test whether candidates can scale top-k selection to a top-rated-businesses leaderboard.

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. Note that it is the kth largest element 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. Sort and index

Sort descending, then return the (k-1)th element.

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

Tradeoff:

2. Min-heap of size k

Maintain a min-heap with the top-k seen so far; the root is always the kth largest. Push new elements and pop when size exceeds k.

Time
O(n log k)
Space
O(k)
class MinHeap {
  constructor() { this.h = []; }
  push(x) { this.h.push(x); this.h.sort((a,b) => a - b); }
  pop() { return this.h.shift(); }
  peek() { return this.h[0]; }
  size() { return this.h.length; }
}
function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const x of nums) {
    heap.push(x);
    if (heap.size() > k) heap.pop();
  }
  return heap.peek();
}

Tradeoff:

Yelp-specific tips

Yelp interviewers will pivot to review ranking — be ready to discuss how a fixed-size heap powers a live top-k leaderboard of trending businesses without re-sorting on every review write.

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 Yelp interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →