Kth Largest Number
You will be given a stream of numbers, and you need to find the kth largest number in the stream at any given time.

As the stream of numbers can not be given during compile time, so you need to design a data structure which can accept infinite numbers and can return the kth largest number at any given time.

The stream of numbers is nothing but a large collection of numbers from which integers are read at runtime, such as the user will never know the upper limit on the number of integers which will be read.

The implemented data structure must support the following operations:

1. add(DATA) : This function should take one argument of type integer and store it in its pool. 2. int getKthLargest() : This function should return the kth largest number from the current pool of integers.

You will be given q queries of 2 types:

1. 1 val - For this type of query, you need to insert the integer into your current pool of integers 2. 2 - For this type of query, you need to return the kth largest integer from the current pool of integers.

Note

1. The maximum number of integers that will be given will always be under memory limits. 2. You will also be given an initial pool of integers whose size will be equal to k. 3. The maximum queries of type 1 will be less than 10^5. 4. The kth largest element is not the kth distinct element but the kth largest element in the sorted order. 5. There will be at least one query of type 2.

Input Format:

The first line contains two space-separated integers 'Q’ and ‘K’, where Q denotes the number of queries which will be run against the implemented data structure. The second line will contain ‘K’ space-separated integers which will be the initial pool of integers. Then Q lines follow. The i-th line contains the i-th query in the format as in the problem statement For the query of the first type, the input line will contain two integers ‘QUERYTYPE’ and ‘DATA’ separated by a single space, representing the type of the operation in integer and the integer data to be included in the pool respectively. For the rest of the queries, the input line will contain only one integer value, representing the query being performed.

Output Format:

For Query-1, you do not need to return anything. For Query-2, prints the kth largest integer from the current pool. The output of each query of type 2 has to be printed in a separate line.

Note:

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

Constraints:

1

Question

Kth Largest Number

You will be given a stream of numbers, and you need to find the kth largest number in the stream at any given time.

As the stream of numbers can not be given during compile time, so you need to design a data structure which can accept infinite numbers and can return the kth largest number at any given time.

The stream of numbers is nothing but a large collection of numbers from which integers are read at runtime, such as the user will never know the upper limit on the number of integers which will be read.

The implemented data structure must support the following operations:

1. add(DATA) :
   This function should take one argument of type integer 
   and store it in its pool.
2. int getKthLargest() :
   This function should return the kth largest number from 
   the current pool of integers.

You will be given q queries of 2 types:

1. 1 val - For this type of query, you need to insert the integer into your current pool of integers
2. 2 - For this type of query, you need to return the kth largest integer from the current pool of integers.

Note

 1. The maximum number of integers that will be given will always be under memory limits.
 2. You will also be given an initial pool of integers whose size will be equal to k.
 3. The maximum queries of type 1 will be less than 10^5.
 4. The kth largest element is not the kth distinct element but the kth largest element in the sorted order.
 5. There will be at least one query of type 2.

Input Format:

The first line contains two space-separated integers 'Q’ and ‘K’,  where Q denotes the number of queries which will be run against the implemented data structure.

The second line will contain ‘K’ space-separated integers which will be the initial pool of integers.

Then Q lines follow. The i-th line contains the i-th query in the format as in the problem statement

For the query of the first type, the input line will contain two integers ‘QUERYTYPE’ and ‘DATA’ separated by a single space, representing the type of the operation in integer and the integer data to be included in the pool respectively.

For the rest of the queries, the input line will contain only one integer value, representing the query being performed.

Output Format:

For Query-1, you do not need to return anything.

For Query-2, prints the kth largest integer from the current pool.

The output of each query of type 2 has to be printed in a separate line.

Note:

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

Constraints:

1 <= Q <= 10 ^ 4
1 <= K <= 10 ^ 5
1 <= QUERYTYPE <= 2
1 <= DATA <= 10 ^ 9 

Time Limit: 1 sec.

Accepted Answer

Approach :

1) We can initialize the queue with the initial pool of numbers and use the queue as min-heap.

2) Initially, as the size of the queue is ‘k’ the top element will be the kth largest element of the pool.

3) When reading numbers at runtime i.e reading integers from the stream, we can add the integer to the queue, and if the size of the queue becomes greater than k, we pop the top element from the queue and then return the top element.

4) The top element was removed.

5) If the added element is less than the current kth largest, then this number will surely come at the top of the queue and we don’t need this number as the previous kth largest is still the kth largest number in the current pool.

TC : O(N * log(K)), where ‘N’ is the maximum number of integers we are reading at run time and ‘K’ is the order of the required number in sorted order.

SC : O(N)

Accepted Answer

Brute Force

The brute force approach for this problem is very trivial.
We can always maintain an array that will hold the integers, sort the array in non-increasing order and return the element present at the kth index(1-based indexing).
The array should be such that it can add elements efficiently, for example, vectors in C++, lists in python, etc. Whenever we receive a query of type 1, we add the element in the array and sort it.
For sorting, we can use the inbuilt sort function in many programming languages such as C++, Java, etc.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the maximum number of integers we are reading at run time.

An auxiliary space is used to store the elements of the array. Therefore, overall space complexity will be O(N)

Time Complexity: OtherExplanation:

O((N ^ 2) * log(N)), where ‘N’ is the maximum number of integers we are reading at run time.

The best sorting algorithm sorts the array of size N in N * log(N) time, so we are sorting after each addition.

Accepted Answer

PriorityQueue

This problem can also be solved using min-heaps where the root element is always the minimum element in the whole tree. As heaps are theoretical data structures, we will use priority_queues which are implemented using heaps only.
We know that when we add an element to the priority queue, the minimum(or the maximum) element in the current queue automatically comes at the top (which is called heapify in heaps). We can use this property to efficiently store the numbers as well as return the kth largest number.
We can initialize the queue with the initial pool of numbers and use the queue as min-heap.
Initially, as the size of the queue is ‘k’ the top element will be the kth largest element of the pool.
When reading numbers at runtime i.e reading integers from the stream, we can add the integer to the queue, and if the size of the queue becomes greater than k, we pop the top element from the queue and then return the top element.
The top element was removed because: let us assume that the added element is greater than equal to the current kth largest element, now we don’t need the current kth largest and any number that is less than the current kth largest number, because the next kth largest will surely be one of the numbers which are greater than the current kth largest.
If the added element is less than the current kth largest, then this number will surely come at the top of the queue and we don’t need this number as the previous kth largest is still the kth largest number in the current pool.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the maximum number of integers we are reading at run time.

As priority queue Is being used to store the elements of the array Therefor, overall space complexity will be O(N)

Time Complexity: OtherExplanation:

O(N * log(K)), where ‘N’ is the maximum number of integers we are reading at run time and ‘K’ is the order of the required number in sorted order.

To insert an element into the queue of size N takes logN time, and as per the approach, the maximum size of the queue will be equal to ‘K’.