Another approach would be to use a counting sort method (less space efficient though ) So , for space efficiency , we can use a bitset .element insertion will take O(n) time in the set (with a space complexity of O(log n) )
so , for the above elements , the bitset will look like (the p# shows the index corresponding to the array) 0p10p2p3p4p5p6p7 Now , start from the 1st element in the bitset , and find the next non- zero element print it ..continue the loop from this element . Not very space efficient I suppose , but it is still O(n) and time is O(n) too . @abhijit reddy Ur simple dp is wrong , you should also process the left part as pointed by juver++ -- 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.
