I think you have confused the statement of this problem. The "(in sorted order)" comment makes no sense because a median is exactly one number. One number is always sorted.
After every stream element is read, you want to be able to get the median of all elements read so far. You're correct that the way to do this is maintain the elements in some kind of sorted data structure where you have O(1) access to the middle element. An array or list will work fine, but each stream element will require O(n) to insert in the sorted order (just as you'd do for insertion sort). It's easy to use a balanced tree instead. This reduces the processing time for each element to O(log n). You must maintain the invariant that the root of the tree is the median, so access time is still O(1). When a new element is read, it goes in either the left or right subtree of the root. This may cause the median to shift by 0 or 1 position in either direction. In this case, you'll always be able to pull the successor or predecessor of the root--whichever is the new median--up to the root by using e.g. AVL rotations. You'd have to prove that this does not make the tree too unbalanced so that the O(log n) insertion is hurt, but I don't think this would be hard. On Jul 24, 10:32 am, jalaj jaiswal <[email protected]> wrote: > You are given a stream of numbers which can be positive or negative. You are > required to provide an operation FIND MEDIAN..which when invoked should be > able return the median of the numbers in stream (in sorted order) in O(1) > time. > > Eg: 0 1 2 3 4 > Right FIND MEDIAN returns 2 as median > > Now input is -2 -4 > So Stream = 0 1 2 3 -2 -2 -4 > Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1 > > -- > With Regards, > Jalaj Jaiswal > +919026283397 > B.TECH IT > IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
