IntermediateHeapsArrays
Kth Largest Element in an Array
Problem
Given an integer array nums and an integer k, return the k-th largest element in the array in sorted order (not the k-th distinct element). For example, in [3,2,1,5,6,4] with k = 2 the answer is 5. Try to do better than sorting the whole array.
Constraints
- 1 ≤ k ≤ n ≤ 10^5
- -10^4 ≤ nums[i] ≤ 10^4
Examples
in: nums = [3,2,1,5,6,4], k = 2
out: 5
in: nums = [3,2,3,1,2,4,5,5,6], k = 4
out: 4
Sorted descending: 6,5,5,4,… — duplicates count separately.
What this tests
- Recognising a selection problem (do not fully sort)
- Min-heap of size k and why it is a *min*-heap
- Quickselect and its average vs worst-case behaviour
- Trade-off discussion: O(n log k) guaranteed vs O(n) expected
- Counting sort when the value range is small
Pattern RecognitionComplexity AnalysisOptimizationCommunication
Progressive hints
Choose how much help you want. Each hint reveals a little more; the pattern is not named until hint 2.
Hint 1Direction
Hint 2Pattern
Hint 3Data structure
Hint 4Algorithm
Hint 5Pseudocode
Solution
Solve in your language
The editor, starter code and solution adapt to the language you pick — C++, JavaScript, TypeScript or Python.
Solve in
Candidate thinking
How a strong candidate reasons through this problem, step by step.
Try the problem yourself first (or run the mock interview), then compare your process against a strong candidate's.
Follow-up engine
Requirements change; so does the right algorithm.
F1
The array is huge and streams in; you must answer "current k-th largest" at any time.
F2
Can you achieve linear time? What are the caveats?
F3
Find the
k largest elements themselves (not just the k-th) in sorted order.F4
Multiple queries with different
k on a static array.