Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Sorting works in O(n log n), but you only need the top k.
  2. 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