Practice › Heap & Priority Queue
Kth Largest Element in an Array
Easy · Heap & Priority Queue · Asked at Amazon, Meta, Microsoft, Google, Flipkart
Print the k-th largest element in the array (in sorted order, not the k-th distinct one).
Input
First line: n k. Second line: n integers.
Output
The k-th largest element.
Constraints
- 1 ≤ k ≤ n ≤ 10^5
- -10^4 ≤ a[i] ≤ 10^4
Keep a min-heap of size k: push each element and pop when the heap has more than k items. Its top is the answer.
Example 1
Input
6 2 3 2 1 5 6 4
Output
5
Example 2
Input
9 4 3 2 3 1 2 4 5 5 6
Output
4
Hints
- Sorting works in O(n log n), but you only need the top k.
- Keep a min-heap of the k largest elements seen so far; its top is the k-th largest.
Approach
Push each element into a min-heap; whenever the heap holds more than k elements, pop the smallest. At the end the heap contains the k largest elements and its minimum (the top) is the k-th largest. Quickselect gives O(n) on average if you need it faster.
Complexity: O(n log k) time · O(k) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
pq.push(x);
if ((int)pq.size() > k) pq.pop();
}
cout << pq.top() << "\n";
return 0;
}Python solution
import sys
import heapq
data = list(map(int, sys.stdin.read().split()))
n, k, a = data[0], data[1], data[2:]
heap = []
for x in a:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
print(heap[0])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
pq.add(sc.nextInt());
if (pq.size() > k) pq.poll();
}
System.out.println(pq.peek());
}
}Solve Kth Largest Element in an Array online · All practice problems