Solved Problem - Kth Largest element

Problem statement

Given an array, $A[]$, consisting of $N$ integers; for a given $K$, find the $K^{th}$ largest element in the array.

Input format

The first line consists of two integers $N$ and $K$ $(1 \leq K \leq N \leq 10^6)$.

The second line consists of $N$ integers representing the array $A[]$ $(1 \leq A[i] \leq 10^6)$.

---

Sample

Input 1

5 1
3 6 5 1 4

Output 1

6

Input 2

5 4
3 6 5 1 4

Output 2

3

---

Explanation

Sample 1: $K = 1$ means the $1^{st}$ largest in the entire array which is 6.

Sample 2: $K = 4$ means the $4^{th}$ element if you sort the array in non-increasing order. i.e $4^{th}$ element in [6 5 4 3 1], which is 3.

---

Brute force

The explanation for sample two suggests a very simple solution:

• Sort the array
• Print the $K^{th}$ number from right

When sorting, taking $O(NlogN)$ time and printing the $K^{th}$ element is a constant time operation.

Time complexity - $O(NlogN)$.