Skip to main content

91. Kth Largest Element in an Array

mediumAsked at Vercel

Find the k-th largest element in an unsorted array. Vercel asks this for the min-heap and quickselect approaches — same shape as picking the top-k by latency in their edge-performance monitor.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; both heap and quickselect expected.
  • Blind (2026-Q1)— Listed in Vercel screen pool.

Problem

Given an integer array nums and an integer k, return the k-th largest element in the array. Note that it is the k-th largest element in the sorted order, not the k-th 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. Sort and pick

Sort descending; return nums[k-1].

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

Tradeoff: Simple but doesn't meet the 'without sorting' follow-up.

2. Min-heap of size k (optimal)

Maintain a min-heap of the k largest. Push new; if size > k, pop the smallest. The root is the k-th largest.

Time
O(n log k)
Space
O(k)
function findKthLargest(nums, k) {
  // JS lacks a built-in heap; simulate with a sorted insertion (slow) or use a real binary heap.
  // For clarity, use a sorted array with binary insert.
  const heap = [];
  for (const n of nums) {
    if (heap.length < k) {
      // binary insert into heap (ascending)
      let lo = 0, hi = heap.length;
      while (lo < hi) { const mid = (lo + hi) >>> 1; if (heap[mid] < n) lo = mid + 1; else hi = mid; }
      heap.splice(lo, 0, n);
    } else if (n > heap[0]) {
      heap.shift();
      let lo = 0, hi = heap.length;
      while (lo < hi) { const mid = (lo + hi) >>> 1; if (heap[mid] < n) lo = mid + 1; else hi = mid; }
      heap.splice(lo, 0, n);
    }
  }
  return heap[0];
}

Tradeoff: O(n log k) heap. Quickselect is O(n) average but O(n^2) worst case.

Vercel-specific tips

Vercel grades whether you mention both the heap and quickselect, and articulate when each is preferable. Heap is easier to code and stable; quickselect is faster average-case but unstable. Bonus signal: noting that with a built-in heap library, the heap version is 5 lines.

Common mistakes

  • Sorting ascending and picking index n-k — works but the convention is descending + index k-1.
  • Off-by-one between k-th index and k count.
  • Pushing to heap before size check — wastes pushes/pops.

Follow-up questions

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

  • Quickselect — O(n) average, O(n^2) worst.
  • Top K Frequent Elements (LC 347).
  • Streaming k-th largest (LC 703) — add(int).

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?

Heap is O(n log k), stable, easy. Quickselect is O(n) average but O(n^2) worst case with bad pivots. For LC, heap is the safer answer.

Why MIN-heap for k-th LARGEST?

We want to keep the k largest. The min-heap's root is the smallest among the kept, which is the threshold we compare new candidates against. After processing, root = k-th largest.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →