20. Kth Largest Element in an Array
mediumAsked at MonzoReturn the kth largest transaction amount in a stream from the customer's spending feed.
By Sam K., 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 = 2Output
5Example 2
Input
nums = [3,2,3,1,2,4,5,5,6], k = 4Output
4Approaches
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.