Kth largest element
Ninja loves playing with numbers. One day Alice gives him some numbers and asks him to find the Kth largest value among them.

Input Format:

The first line of input contains an integer ‘T,’ denoting the number of test cases. The test cases follow. The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the number of elements in the array and the index of the largest number to be found respectively.

Output Format:

For each test case, print an integer denoting the Kth largest number. Print the output of each test case in a separate line.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1

Question

Kth largest element

Ninja loves playing with numbers. One day Alice gives him some numbers and asks him to find the Kth largest value among them.

Input Format:

The first line of input contains an integer ‘T,’ denoting the number of test cases. The test cases follow.

The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the number of elements in the array and the index of the largest number to be found respectively.

Output Format:

For each test case, print an integer denoting the Kth largest number.

Print the output of each test case in a separate line.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1<= T <= 50
1 <= K <= N <= 10^4
1 <= array[i] <= 10^5

Time Limit: 1 sec

Accepted Answer

Sorting

The idea is to sort the elements and return the kth largest element among them.

The steps are as follows:

Sort the elements in descending order.
Return the element at k - 1 th index.

Space Complexity: O(1)Explanation:

O(1), no extra space required.

As we are not using any extra space. Hence, the overall space complexity is O(1).

Time Complexity: O(nlogn)Explanation:

O(N*logN), where ‘N’ is the total number of elements in the given array.

As Sorting takes N*LogN complexity, so the overall complexity is O(N*logN).

Python (3.5)

'''

    Time Complexity: O(N*log N)

    Space Complexity: O(1)



    Where 'N' denotes the number of elements of the array

'''





def findKthLargest(nums, k):



    # Sorting the elements to get kth largest element

    nums = sorted(nums, reverse = True)



    return nums[k - 1]

C++ (g++ 5.4)

/*

    Time Complexity: O(N*log N)

    Space Complexity: O(1)



    Where 'N' denotes the number of elements of the array

*/



int findKthLargest(vector < int > & nums, int k) {



  // Sorting the elements to get kth largest element

  sort(nums.begin(), nums.end(), greater < int > ());



  return nums[k - 1];

}

Java (SE 1.8)

/*

    Time Complexity: O(N*log N)

    Space Complexity: O(1)



    Where 'N' denotes the number of elements of the array

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution {



	public static int findKthLargest(ArrayList nums, int k) {





		// Sorting the elements to get kth largest element

		Collections.sort(nums, Collections.reverseOrder());



		return nums.get(k - 1);

	}

}

Accepted Answer

Priority queue

We can insert the elements in a priority queue and remove the k top elements to get our desired result.

The steps are as follows:

Initialize a priority queue ‘elementsInserted’ to store the elements based on priority.
We will iterate from i = 0 to N:
- If k elements are already inserted in ‘elementsInserted’ then we check if array[i] is greater than equal to the top element of ‘elementsInserted’, then we remove an element from ‘elementsInserted’ and insert array[i] in ‘elementsInserted’.
- Else we just insert array[i] in ‘elementsInserted’.
Finally, we return the topmost element of the ‘elementsInserted’ as our final answer.

Space Complexity: OtherExplanation:

O(K), where ‘K’ is the index of the largest number to be removed.

As we are using a priority queue to store the elements and storing maximum ‘K’ elements. Hence, the overall space complexity is O(K).

Time Complexity: OtherExplanation:

O(N*log K), where ‘N’ is the total number of elements in the given array and ‘K’ is the index of the largest number to be found.

As we are iterating over all the elements of the array it takes at most ‘N’ time and inserting and removing elements from the queue takes log K time, so the overall time complexity is O(N*log K).