it can be solved in o(n) , keep one pointer at start and another pointer at the last , traverse the string if u get R swap it at the start position and then increament it , if u get B swap it with last pointer pointing to last position .and then decrement it . in this way all things will come in place .
On Sat, Jun 9, 2012 at 11:36 PM, Navin Kumar <[email protected]>wrote: > Given a character array as input. Array contains only three types of > characters 'R', 'G' and 'B'. Sort the array such that all 'R's comes before > 'G's and all 'G's comes before 'B's. > > Constraint :- No extra space allowed(except O(1) space like variables) and > minimize the time complexity. > You can only traverse the array once. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/54GHWSwHHw8J. > 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. > -- Cheers, Nishant Pandey |Specialist Tools Development | [email protected]<[email protected]> | +91-9911258345 -- 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.
