Skip to main content

17. Kth Largest Element in an Array

mediumAsked at Riot Games

Return the kth largest element in an unsorted array — Riot tests this pattern when reasoning about leaderboard top-k queries and Elo bucket cutoffs.

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's the kth largest by 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 and return index 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

Maintain a min-heap of size k; the root is the kth largest after processing all elements. Riot uses the same bounded heap to track top-k Elo/Glicko leaderboards without sorting the full player table.

Time
O(n log k)
Space
O(k)
class MinHeap {
  constructor(){this.h=[];}
  push(v){this.h.push(v);this._up(this.h.length-1);}
  pop(){const t=this.h[0];const e=this.h.pop();if(this.h.length){this.h[0]=e;this._down(0);}return t;}
  peek(){return this.h[0];}
  size(){return this.h.length;}
  _up(i){while(i>0){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;}}
  _down(i){const n=this.h.length;while(true){let l=2*i+1,r=l+1,s=i;if(l<n&&this.h[l]<this.h[s])s=l;if(r<n&&this.h[r]<this.h[s])s=r;if(s===i)break;[this.h[s],this.h[i]]=[this.h[i],this.h[s]];i=s;}}
}
function findKthLargest(nums,k){
  const h = new MinHeap();
  for (const n of nums){
    h.push(n);
    if (h.size()>k) h.pop();
  }
  return h.peek();
}

Tradeoff:

Riot Games-specific tips

Riot expects you to default to a size-k heap because it matches their leaderboard service — Elo/Glicko queries care about the top bucket, not the entire sorted player base.

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

Practice these live with InterviewChamp.AI →