About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career

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)

Attend our Free Webinar on How to Nail Your Next Technical Interview

Recommended Posts

All Posts