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
#Capgemini#SeniorSoftwareEngineer
1 views
Answers (2)

Submit your answer

CodingNinjas
CodingNinjas
Answered Mar 09, 2022
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);
}
}
Report

CodingNinjas
CodingNinjas
Answered Mar 09, 2022
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).


Java (SE 1.8)
/*

Time complexity: O(N * log(K))
Space complexity: O(K)

where K is the position (ordered by increasing value) of the element you need to find
*/

import java.util.ArrayList;
import java.util.PriorityQueue;

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

// Initialising min heap
PriorityQueue elementsInserted = new PriorityQueue();

// Loop to find kth largest element
for (int i = 0; i < nums.size(); i++) {

// If size of priority queue equals k then remove the small elements from the queue
if (elementsInserted.size() == k) {
if (nums.get(i) >= elementsInserted.peek()) {
elementsInserted.poll();
elementsInserted.add(nums.get(i));
}
} else {
elementsInserted.add(nums.get(i));
}
}
// Return the Kth largest element
return elementsInserted.peek();
}
}

Python (3.5)
'''

Time Complexity: O(N*log N)
Space Complexity: O(1)

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

import heapq

def findKthLargest(nums, k):

# Initialising min heap
elementsInserted = []

# Loop to find kth largest element
for i in range(len(nums)):

# If size of priority queue equals k then remove the small elements from the queue
if len(elementsInserted) == k:
if nums[i] >= elementsInserted[0]:
heapq.heappop(elementsInserted)
heapq.heappush(elementsInserted, nums[i])

else:
heapq.heappush(elementsInserted, nums[i])

# Return the Kth largest element
return elementsInserted[0]



C++ (g++ 5.4)
/*

Time complexity: O(N * log(K))
Space complexity: O(K)

Where 'K' is the position (ordered by increasing value) of the element you need to find
and 'N' is the number of elements of the array
*/

#include

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

// Initialising min heap
priority_queue < int, vector < int > , greater < int > > elementsInserted;

// Loop to find kth largest element
for (int i = 0; i < nums.size(); i++) {

// If size of priority queue equals k then remove the small elements from the queue
if (elementsInserted.size() == k) {
if (nums[i] >= elementsInserted.top()) {
elementsInserted.pop();
elementsInserted.push(nums[i]);
}
} else {
elementsInserted.push(nums[i]);
}
}
// Return the Kth largest element
return elementsInserted.top();
}
Report

Report Interview Advice

What’s wrong with this interview advice?