Kth Largest Element in an Array
On this page
Problem statement
Given an unsorted array of integers and a number k, return the k-th largest element. This means the k-th largest in sorted order, not the k-th distinct value: in [3, 3, 1], the 2nd largest is 3. Try to do better than sorting the whole array.
This is the standard question for comparing a heap with quickselect, and for explaining average versus worst-case complexity. Original problem: LeetCode 215.
Example

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4
Constraints (assumed)
- 1 ≤ k ≤ n ≤ 100,000.
- −10⁴ ≤ value ≤ 10⁴.
What this question tests
- Choosing between sorting, a heap and quickselect, and explaining the trade-offs.
- Getting the heap direction right (a min-heap for the largest values).
- Understanding average vs. worst case and how randomization helps.
Questions to ask first
- k-th largest counting duplicates, or k-th distinct? (Here: counting duplicates.)
- Can I modify the array? Quickselect reorders it in place.
- Is k small compared with n? A size-k heap shines when k ≪ n.
- Is the data a stream? Then the heap is the natural fit.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.