Get K Max and Delete K Max in stream of Incoming Integers
1) Keep a Min & Max Heap of K size 2) Store first K elements in them. 3) If a new element comes with smaller or larger than root then reorder heap.
|Min heap||Max heap|
-O(1) for search First Minimum/Maximum.
-To get second Min/Max we need to Delete Min/Max element reordering takes O(log N) and again we can Find second Min/Max in O(1).
– To insert new Min/Max element takes O(log N)
Solution 2: Using Linked List or Queue.
Whenever new number x comes, check if x < head -> data than (in case of 0 here) create node Temp Temp->next = head Temp = Head. remove rear (to keep K size constant) else of x < rear -> data than (in case of 2 here) create new Temp node traverse link list and put Temp at appropriate node (insert) remove rear (to keep K size constant)