Problem

Submissions

Hints & solutions

Discuss

Kth Largest Element In A Stream

Moderate

0/80

Average time to solve is 30m

Contributed by

32 upvotes

Asked in companies

Problem statement

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 that will be read.

The implemented data structure must support the following operations:

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

You will be given 'q' queries:

val - For this query, insert the integer into your current pool of integers and return the 'kth' largest integer from the existing 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 equals k.

 3. The maximum number of queries 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.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains two space-separated integers, 'Q’ and ‘K’,  where 'Q' denotes the number of queries running 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 an integer ‘DATA’, 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 each query, prints the 'kth' largest integer from the current pool.

The output of each query 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.

Sample Input 1:

Sample Output 1:

2
3

Explanation of the Sample Input1:

The initial pool is - 2 1 3. 

When 3 is added, the pool is now  - 3 2 1 3. The 3rd largest element is 2(when we sort the pool, it becomes 3 3 2 1).

When 5 is added, the pool is now - 5 3 2 1 3. Even now, the 3rd largest element is 3(when we sort the pool, it becomes 5 3 3 2 1).

Sample Input 2:

1 5
4 4 4 4 2
3

Sample Output 2:

Constraints:

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

Time Limit: 1 sec.

Hint 1

Hint 2

Try maintaining the sorted order of the current pool.

Approaches (2)

Approach 1

Approach 2

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.

Time Complexity

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.

Space Complexity

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)

(75% EXP penalty)

(100% EXP penalty)

Kth Largest Element In A Stream

Console