Top Kth Problem

You are given an array of integers, arr, of size n, which is analogous to a continuous stream of integers input. Your task is to find K largest elements from a given stream of numbers. 

By definition, we don't know the size of the input stream. Hence, produce K largest elements seen so far, at any given time. For repeated numbers, return them only once.

If there are less than K distinct elements in arr, return all of them.

- Don't rely on size of input array arr.

- Feel free to use built-in functions if you need a specific data-structure.

Example One

Input: arr = [1, 5, 4, 4, 2]; K = 2

Output: [4, 5]

Example Two

Input: arr = [1, 5, 1, 5, 1]; K = 3

Output: [5, 1]

Notes

Input Parameters: There is only one argument: Integer array arr.

Output: Return an integer array res, containing K largest elements. If there are less than K unique elements, return all of them. Order of elements in res does not matter.

Constraints:

● 1

● 1

● arr may contain duplicate numbers.

● arr may or may not be sorted

Solutions:

We need to preserve the order of elements in a sorted manner. If we can do that, we can obtain top K elements. Also, if an element is smaller than the last element in top k, then that element can be dropped as we are not deleting elements.

We can maintain a balanced BST or a sorted set collection. Keep adding new elements to the sorted set and if the size of the tree increases more than k, remove the smallest element.

Time Complexity: 

O(N*log(K))

Space Complexity: 

O(K)