Monday, December 27, 2010

Kth largest element for a stream of integers

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.



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)

12 comments :

  1. Binary Search Tree or C++ Bitset.

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

    ReplyDelete
  3. Well,in case of BST:

    Keep 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.

    ReplyDelete
  4. 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.....

    Look for some more efficient solution
    Insertion log(k)
    Kth largest element O(1)

    regards

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

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

    ReplyDelete
  6. @imavalon ... nice solution !!!

    ReplyDelete
  7. How using Min Heap kth largest will be accessed in O(1)?

    ReplyDelete
  8. Here 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?

    ReplyDelete
  9. k is constant for a given problem .......

    ReplyDelete
  10. We 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 .....

    ReplyDelete
  11. 2
    / \
    3 4
    / \ / \
    7 15 10 12
    Heapsize = 7;
    Now How 7th Largest elememt will be retrieved in o(1) time?

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

    ReplyDelete