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.
Input: arr = [1, 5, 4, 4, 2]; K = 2
Output: [4, 5]
Input: arr = [1, 5, 1, 5, 1]; K = 3
Output: [5, 1]
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.
● 1 <= n <= 10^5
● 1 <= K <= 10^5
● arr may contain duplicate numbers.
● arr may or may not be sorted
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.
O(N*log(K))
O(K)
