Skip to main content

20. Kth Largest Element in an Array

mediumAsked at ByteDance

Find the kth largest value in an unsorted array — ByteDance uses it to test heap vs quickselect tradeoffs that show up in their ranking-cutoff systems.

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

Sort the array descending and return index k-1.

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

Tradeoff:

2. Min-heap of size k

Maintain a min-heap of the k largest values seen so far; the root is the kth largest at the end.

Time
O(n log k)
Space
O(k)
function findKthLargest(nums, k) {
  const heap = [];
  const up = (i) => { 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; } };
  const down = (i) => { const n = heap.length; for (;;) { const l = i * 2 + 1, r = l + 1; let s = i; if (l < n && heap[l] < heap[s]) s = l; if (r < n && heap[r] < heap[s]) s = r; if (s === i) break; [heap[s], heap[i]] = [heap[i], heap[s]]; i = s; } };
  for (const v of nums) {
    heap.push(v); up(heap.length - 1);
    if (heap.length > k) { heap[0] = heap.pop(); down(0); }
  }
  return heap[0];
}

Tradeoff:

ByteDance-specific tips

ByteDance interviewers grade the cost discussion harder than the code — be ready to compare quickselect's O(n) average against the heap's worst-case guarantee for ranking pipelines.

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

Practice these live with InterviewChamp.AI →