Skip to main content

18. Kth Largest Element in an Array

mediumAsked at N26

Return the kth largest element in an unsorted array. N26 frames this as picking the kth biggest transaction in a daily settlement batch for variance reporting.

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

Problem

Given an integer array nums and an integer k, return the kth largest element. Note that it 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 index at 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

Push items onto a min-heap of size k; pop the smaller value once size exceeds k. The heap's root at the end is the kth largest. Beats O(n log n) when k is small relative to n.

Time
O(n log k)
Space
O(k)
function findKthLargest(nums, k) {
  const h = []; // min-heap by value
  const 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; } };
  const down = i => { for(;;){ let l=2*i+1, r=2*i+2, s=i; if(l<h.length&&h[l]<h[s])s=l; if(r<h.length&&h[r]<h[s])s=r; if(s===i)break; [h[s],h[i]]=[h[i],h[s]]; i=s; } };
  for (const n of nums) {
    h.push(n); up(h.length-1);
    if (h.length > k) { h[0] = h.pop(); down(0); }
  }
  return h[0];
}

Tradeoff:

N26-specific tips

N26 likes when you note that the streaming heap variant fits their settlement-variance dashboard, where they only ever need the top-k outlier transactions per currency bucket.

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

Practice these live with InterviewChamp.AI →