Kth Largest Element in an Array

Given an integer array nums and an integer k, return the k^th largest element in the array.

Note that it is the k^th largest element in the sorted order, not the k^th distinct element.

Input Format

First Parameter: number n

Second Parameter - array nums of size n

Third Parameter - number k

Output Format

Return the number.

Example 1

Input :
    6
    3 2 1 5 6 4
    2

Output : 
    5

Example 2

Input : 
    9
    3 2 3 1 2 4 5 5 6
    4

Output : 
    4

Constraints:

• 1 <= k <= n <= 10⁴.
• -10⁴ <= nums[i] <= 10⁴.
• Expected Time Complexity : O(nlogk).
• Expected Space Complexity : O(k)