Skip to main content

20. Kth Largest Element in an Array

mediumAsked at Monzo

Return the kth largest transaction amount in a stream from the customer's spending feed.

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. Can you solve it without sorting?

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

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

Tradeoff:

2. Min-heap of size k

Maintain a min-heap of the k largest seen so far; the heap root is the kth largest after one pass.

Time
O(n log k)
Space
O(k)
function findKthLargest(nums, k) {
  const h = [];
  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 => { const n = h.length; while (true) { const l = 2*i+1, r = 2*i+2; let 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:

Monzo-specific tips

Monzo wants the heap version explained as a streaming algorithm because their spending-analytics pipeline is bounded-memory.

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

Practice these live with InterviewChamp.AI →