Skip to main content

16. Kth Largest Element in an Array

mediumAsked at Baidu

Find the kth largest element in an unsorted array without fully sorting it.

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 the array

Sort descending and return index k-1.

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 of size k; the root after one pass is the kth largest.

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

Tradeoff:

Baidu-specific tips

Baidu uses k-heaps to pick top-k ad-ranking candidates in real time, so they grade you on choosing size-k heap (O(n log k)) over quickselect when k is small relative to n.

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

Practice these live with InterviewChamp.AI →