Skip to main content

10. Kth Largest Element in an Array

mediumAsked at JetBrains

Return the kth largest element without fully sorting — JetBrains uses this to gauge whether you can pick the right partial-sort primitive for top-N completion ranking.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums and integer k, return the kth largest element. 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. Full sort

Sort descending and pick index k-1; throws away most of the work.

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

Tradeoff:

2. Min-heap of size k

Keep a min-heap of size k; the root is the kth largest. Same shape as JetBrains's top-N completion ranker maintaining bounded result buffers.

Time
O(n log k)
Space
O(k)
function findKthLargest(nums, k) {
  const heap = [];
  const up = i => { while (i>0) { const p=(i-1)>>1; if (heap[p]>heap[i]) { [heap[p],heap[i]]=[heap[i],heap[p]]; i=p; } else break; } };
  const down = i => { const n=heap.length; while (true) { let s=i, l=2*i+1, r=2*i+2; if (l<n&&heap[l]<heap[s]) s=l; if (r<n&&heap[r]<heap[s]) s=r; if (s===i) break; [heap[s],heap[i]]=[heap[i],heap[s]]; i=s; } };
  for (const n of nums) {
    heap.push(n); up(heap.length-1);
    if (heap.length>k) { heap[0]=heap.pop(); if (heap.length) down(0); }
  }
  return heap[0];
}

Tradeoff:

JetBrains-specific tips

JetBrains expects you to mention bounded top-K maintenance — IDE completion rankers must surface the best K candidates without sorting the entire symbol universe.

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

Practice these live with InterviewChamp.AI →