You are reading a stream of integers and you cannot look back to the stream once it is passed. At any instant you have to find the kth largest element(if the stream is less than k you need to report smallest element) from the stream read so far. What is data structure you will use and approach to find the same.

Maintain a min heap of size k and insert the incoming stream elements in the heap. kth largest is the root element in the heap

Time complexity: Insertion O(1), Insertion O(log k)

Space complexity: O(k)

**Approach:**Maintain a min heap of size k and insert the incoming stream elements in the heap. kth largest is the root element in the heap

Time complexity: Insertion O(1), Insertion O(log k)

Space complexity: O(k)

Binary Search Tree or C++ Bitset.

ReplyDeleteexplain ur approach also .. for the insertion of element and the removal of min element and their time and space complexity

ReplyDeleteWell,in case of BST:

ReplyDeleteKeep inserting the elements following the rules of BST and maintain a counter to keep track how many elements are inserted.

If duplicate appears then just discard it.

now if counter<k,then return the leftmost element of the BST

else the kth largest element can be returned by doing a inorder traversal of the tree.

C++ Bitset,I think will not be so much handy.As we dont know the range.Otherwise it can be implemented like this:

Suppose the appearing no is n.

Then set the nth bit.

Return the kth set bit.

In case of BST you will be using up extra space to keep the counter ... further ur approach requires O(n) cost in insertion and O(k) cost in finding the kth largest element.....

ReplyDeleteLook for some more efficient solution

Insertion log(k)

Kth largest element O(1)

regards

min heap of size k. kth largest in O(1), insertion O(log k) ,memory O(k).

ReplyDeletewith a balanced bst you can obtain the kth largest in O(log n) and insertion O(log n) with O(n) memory.

@imavalon ... nice solution !!!

ReplyDeleteHow using Min Heap kth largest will be accessed in O(1)?

ReplyDeleteHere you are assuming that k is constant. But what will happen when at any instant I want the 15th largest element and after sometimes I want 20 th largest element?

ReplyDeletek is constant for a given problem .......

ReplyDeleteWe can get kth largest element using min heap by maintaining a heap of k size and at any instant we can find kth largest by looking at the root node .....

ReplyDelete2

ReplyDelete/ \

3 4

/ \ / \

7 15 10 12

Heapsize = 7;

Now How 7th Largest elememt will be retrieved in o(1) time?

7th largest element is 2 ... that is the root node of the heap which can be accessed in O(1)

ReplyDelete