Skip to main content

20. Kth Largest Element in an Array

mediumAsked at Autodesk

Find the kth largest element in an unsorted array.

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 this 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 descending

Sort and index k-1.

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

Tradeoff:

2. Min-heap of size k

Keep a size-k min-heap of the largest values seen so far. When the heap is full and you encounter a bigger value, pop the smallest. The heap top at the end is the answer.

Time
O(n log k)
Space
O(k)
class MinHeap {
  constructor(){ this.a = []; }
  push(x){ this.a.push(x); this._up(this.a.length-1); }
  pop(){ const t=this.a[0]; const l=this.a.pop(); if (this.a.length){ this.a[0]=l; this._down(0);} return t; }
  peek(){ return this.a[0]; }
  size(){ return this.a.length; }
  _up(i){ while(i>0){ const p=(i-1)>>1; if(this.a[p]>this.a[i]){ [this.a[p],this.a[i]]=[this.a[i],this.a[p]]; i=p;} else break; } }
  _down(i){ const n=this.a.length; while(true){ const l=2*i+1,r=l+1; let s=i; if(l<n&&this.a[l]<this.a[s]) s=l; if(r<n&&this.a[r]<this.a[s]) s=r; if(s!==i){[this.a[i],this.a[s]]=[this.a[s],this.a[i]]; i=s;} else break; } }
}
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:

Autodesk-specific tips

Heaps are core to Autodesk's BVH traversal (ray-vs-bounding-box priority queues), so handling them by hand earns bonus signal.

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

Practice these live with InterviewChamp.AI →