well doing it in O(n) is a research problem...
stackoverflow.com/questions/15400585/in-place-sort-an-array-with-2-sorted-sub-arrays
it's not that easy... for given problem quicksort or heapsort would work
fine...
On May 27, 2013 7:48 PM, bharat b bagana.bharatku...@gmail.com wrote:
@Nishan :
Create a BST from given list such that team that has won should be
right child of node and and teams that has lost should be left child
of node and then traverse the tree in reverse in order.
Karan
On Thu, May 23, 2013 at 10:58 PM, bharat b bagana.bharatku...@gmail.com wrote:
@Don : you are
It' similar to implement min in O(1) in stack.
http://stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1
suppose you have implemented stack through linked list.
you can maintain another stack in parallel (say midstack)where you
keep the pointer of middle element
@nishant: I think this won't work in all the cases as you said in a
statement: one or two element won't be at correct positions.. there
might be more in other cases unless you prove it somehow. what if
array is too large and there are too many elements not at correct
position after second pass.