← All coding problems
Kth Largest Element in an Array
mediumHeap / Priority Queue+20 XPTime limit 2s
Find the k-th largest element of the array — the k-th element in sorted (descending) order, counting duplicates (in 3 2 3 1 2 4 5 5 6 the 4th largest is 4).
Input:
- line 1:
n k - line 2:
nintegers
Output: the k-th largest value.
Constraints: 1 ≤ k ≤ n ≤ 10⁵, −10⁴ ≤ value ≤ 10⁴.
Three ways: sort (O(n log n)); a min-heap of size k — its top is the answer (O(n log k)); or Quickselect (average O(n)). Try all three.
Sample input 1
6 2 3 2 1 5 6 4
Sample output 1
5
Sample input 2
9 4 3 2 3 1 2 4 5 5 6
Sample output 2
4
📖 Stuck? Learn the pattern
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).