heaps · Problem 1 of 2
Kth Largest Element
medium
Amazon
Meta
Google
AmazonMetaGoogleReturn the kth largest value in nums (1-indexed, so k = 1 is the maximum).
findKthLargest([3, 2, 1, 5, 6, 4], 2) -> 5Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Running is free — Submit is what records it. Or press ⌘↩
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| findKthLargest([3,2,1,5,6,4], 2) | second largest | 5 | — |
| findKthLargest([3,2,1], 1) | largest | 3 | — |
| findKthLargest([3,3,3], 2) | with duplicates | 3 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n log n) as written; O(n log k) with a size-k heap
- target space
- O(n) as written; O(k) with a heap
The sorting solution passes and is worth writing first. The heap version is the interview answer: you never need the whole array ordered, only the top k.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left