Skip to main content

17. Kth Largest Element in an Array

mediumAsked at Byju's

Return 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 the sorted order, not the kth distinct element. Try to solve it without sorting the whole array.

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 and return nums[k-1].

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

Keep a min-heap of the top k largest values; the root is the kth largest. Each push is O(log k).

Time
O(n log k)
Space
O(k)
class Heap {
  constructor(){this.h=[];}
  push(v){this.h.push(v);let i=this.h.length-1;while(i){const p=(i-1)>>1;if(this.h[p]<=this.h[i])break;[this.h[p],this.h[i]]=[this.h[i],this.h[p]];i=p;}}
  pop(){const t=this.h[0],l=this.h.pop();if(this.h.length){this.h[0]=l;let i=0;for(;;){const a=2*i+1,b=a+1;let m=i;if(a<this.h.length&&this.h[a]<this.h[m])m=a;if(b<this.h.length&&this.h[b]<this.h[m])m=b;if(m===i)break;[this.h[m],this.h[i]]=[this.h[i],this.h[m]];i=m;}}return t;}
}
function findKthLargest(nums, k){
  const heap = new Heap();
  for(const n of nums){ heap.push(n); if(heap.h.length>k) heap.pop(); }
  return heap.h[0];
}

Tradeoff:

Byju's-specific tips

Byju's adaptive-learning rankers run top-k cohort comparisons nightly, so frame the heap solution as 'top-k learner score selection' to land 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 Byju's interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →