Skip to main content

20. Kth Largest Element in an Array

mediumAsked at GitLab

Return the kth largest element of an unsorted array, ideally 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. It 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. Sort and index

Sort descending, return nums[k-1]. Simple but O(n log n).

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

Tradeoff:

2. Min-heap of size k

Maintain a min-heap of size k; the root is the kth largest at the end. Streams cleanly and is what GitLab expects for a runner-pool top-k.

Time
O(n log k)
Space
O(k)
class MinHeap {
  constructor(){ this.a = []; }
  size(){ return this.a.length; }
  peek(){ return this.a[0]; }
  push(v){ this.a.push(v); this._up(this.a.length - 1); }
  pop(){ const top = this.a[0], last = this.a.pop();
    if (this.a.length){ this.a[0] = last; this._down(0); } return top; }
  _up(i){ while (i){ const p = (i-1)>>1; if (this.a[p] <= this.a[i]) break;
    [this.a[p], this.a[i]] = [this.a[i], this.a[p]]; i = p; } }
  _down(i){ const n = this.a.length; while (true){
    const l = 2*i+1, r = 2*i+2; let m = i;
    if (l < n && this.a[l] < this.a[m]) m = l;
    if (r < n && this.a[r] < this.a[m]) m = r;
    if (m === i) break;
    [this.a[m], this.a[i]] = [this.a[i], this.a[m]]; i = m; } }
}
function findKthLargest(nums, k){
  const h = new MinHeap();
  for (const x of nums){ h.push(x); if (h.size() > k) h.pop(); }
  return h.peek();
}

Tradeoff:

GitLab-specific tips

GitLab will ask how this maps to picking the k slowest jobs from a runner-pool telemetry stream — they want the O(n log k) heap answer, not the sort.

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

Practice these live with InterviewChamp.AI →