Skip to main content

12. Kth Largest Element in an Array

mediumAsked at Confluent

Find the kth-largest value in an unsorted array — Confluent uses it to probe heap intuition, which lines up with top-K streaming aggregates over a Kafka topic.

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.

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

Sort descending and return index k-1.

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

Tradeoff:

2. Size-k min-heap

Maintain a min-heap of size k while scanning. Push each value and pop when size exceeds k. The root at the end is the answer in O(n log k) time.

Time
O(n log k)
Space
O(k)
function findKthLargest(nums, k) {
  const h = []; // simple min-heap; use a library in real code
  function up(i){while(i>0){const p=(i-1)>>1; if(h[p]<=h[i])break; [h[p],h[i]]=[h[i],h[p]]; i=p;}}
  function down(i){const n=h.length; for(;;){let l=2*i+1,r=l+1,s=i; if(l<n&&h[l]<h[s])s=l; if(r<n&&h[r]<h[s])s=r; if(s===i)break; [h[s],h[i]]=[h[i],h[s]]; i=s;}}
  for (const x of nums) {
    h.push(x); up(h.length-1);
    if (h.length > k) { h[0] = h.pop(); down(0); }
  }
  return h[0];
}

Tradeoff:

Confluent-specific tips

Confluent will ask how this scales over a Kafka topic — describe how each partition keeps its own size-k heap and a downstream consumer merges them, so consumer-group rebalance never loses the global top-K.

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

Practice these live with InterviewChamp.AI →