Kth Largest Element in an Array
You are given an array consisting of 'N' distinct positive integers and a number 'K'. Your task is to find the kth largest element in the array.

Example:

Consider the array {2,1,5,6,3,8} and 'K' = 3, the sorted array will be {8, 6, 5, 3, 2, 1}, and the 3rd largest element will be 5.

Note:

1) Kth largest element in an array is the kth element of the array when sorted in non-increasing order. 2) All the elements of the array are pairwise distinct.

Input Format:

The first line of the input contains an integer 'T' denoting the number of test cases. The first line of each test case contains two space- separated integers 'N' and 'K', as described in the problem statement. The second line of each test case contains 'N' space-separated integers, representing the elements of the array.

Output Format:

For each test case, print a single integer denoting the kth largest number in the given array.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Kth Largest Element in an Array

You are given an array consisting of 'N' distinct positive integers and a number 'K'. Your task is to find the kth largest element in the array.

Example:

Consider the array {2,1,5,6,3,8} and 'K' = 3, the sorted array will be {8, 6, 5, 3, 2, 1}, and the 3rd largest element will be 5.

Note:

1) Kth largest element in an array is the kth element of the array when sorted in non-increasing order. 

2) All the elements of the array are pairwise distinct.

Input Format:

The first line of the input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains two space- separated integers 'N' and 'K', as described in the problem statement.

The second line of each test case contains 'N' space-separated integers, representing the elements of the array.

Output Format:

For each test case, print a single integer denoting the kth largest number in the given array.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 10^4
1 <= ARR[i] <= 10^9
1 <= K <= N

Time Limit: 1 sec

Accepted Answer

To solve the question using a max heap, make a max heap of all the elements of the list. Run a loop for k-1 times and remove the top element of the heap. After running the loop, the element at top will be the kth largest element, return that. Time Complexity : O(n + klogn)

The question can also be solved using a min heap.

Approach :

1. Create a min heap class with a capacity of k

2. When the heap reaches capacity eject the minimum number.

3. Loop over the array and add each number to the heap.

4. At the end, the largest k number of elements will be left in the heap, the smallest of them being at the top of the heap, which is the kth largest number

The time complexity for this solution is O(N logK).

Accepted Answer

Brute Force

The most obvious brute force approach would be to sort the array in descending order and return the ‘K’th element from the beginning of the array.
Sort the array in descending order, for sorting most of the languages have their inbuilt sort methods which are usually very fast.
After sorting, return the element arr['K'-1](i.e. element at index ‘K’-1, considering 0-based indexing).

Space Complexity: O(1)Explanation:

O(1).

No extra space is used.

Time Complexity: O(nlogn)Explanation:

O( N * log(N) ), where ‘N’ is the size of the array.

We can sort an array in O(N * log(N)).

Accepted Answer

Priority Queue(Min-Heap)

We can use some data structures to reduce the time complexity. Notice the fact that if there are only ‘K’ elements in the array, then the ‘K’th largest element will be nothing but the smallest element of that array. This observation clearly hints at using heaps as they help find either the minimum or maximum element efficiently.
We will be using a min-heap as we are interested in the smallest element among the ‘K’ largest elements of the array. In most of the programming languages, heaps are implemented using priority queues.
Maintain a priority queue giving priority to the min element( Min-heap), and insert the first ‘K’ elements of the array into the priority queue.
Now traverse the remaining ‘N - K’ elements one by one and check if the element at the top of the priority queue is smaller than the element being traversed then pop the element present at the top of the queue and insert the element being traversed in the priority queue. And do the same for all the ‘ N - K ’ elements. We want to make sure that at any instance our queue will only have ‘K’ elements.
After performing the above operation, return the element at the top of the priority queue, which will be our answer. Because after performing the above operations the priority queue will be containing the ‘K’ largest elements of the array. And the min of these ‘K’ elements will be the kth largest element which will be present at the top of the queue because we are maintaining a min priority queue (min-heap).

Lets examine the working of the above algorithm with the help of an example:

Consider the array {2,3,4,8,1,7,5,6} and let ‘K’ =4.

Lets take an empty priority queue(min heap)

After performing the first step of the algorithm the queue will be:

2-3-4-8 (in the same order i.e. 2 will be at the top of the queue and 8 at the bottom).

Now we start traversing the rest of the ‘N - K’ elements i.e step2 of the algorithm.
We start form 1, since it is smaller than 2 so we will continue.
Then we come to 7, since it is greater than 2 so we will pop the element from the top(2) and push 7 into the queue. Now, queue will be like 3-4-7-8(in the same order).
Then we come to 5, since it is greater than 3 so we will pop the element from the top of the queue(3) and push 5 into the queue. Now, queue will be like 4-5-7-8 (in the same order).
Then we come to 6, since it is greater than 4 so we will pop the element from the top of the queue(4) and push 6 into the queue. Now, queue will be like 5-6-7-8 (in the same order).
After completing this step we can observe that our queue contains the 4 largest elements of the array with the 4th largest element at the top of the queue.
Now we return the element at the top of the queue(5) which is our answer.

Space Complexity: OtherExplanation:

O(K), where ‘K’ is the order of the largest element to be found.

We are storing only ‘K’ elements in the heap thus O(K) space complexity.

Time Complexity: OtherExplanation:

O( K + (N - K) * log(K) ), where ‘N' is the size of the array, and ‘K’ is the order of the largest element to be found.

Building a min-heap of ‘K’ elements will take O(K), and then check for (N - K) remaining elements, we need to compare it with the top of the heap, which in the worst case can take O( (N-K) * Log(K) ) as we need to insert (N-K) elements in the min-heap.

You are given an array consisting of 'N' distinct positive integers and a number 'K'. Your task is to find the kth largest element in the array.

Example:

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Uber Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Uber Software Engineer