Just use the counting sort and keep the counts in variables int R, int G, int B.
Traverse the array and increment each respective variable (R or G or B) as soon as you encounter upon it. Once finished, you will have all the counts of frequencies stored in those three variables. Now, start traversing the array of counts (R, G, B) and fill the original array with data. Space O(1), time O(N) Rgds, Ashot Madatyan From: algogeeks@googlegroups.com [mailto:algogeeks@googlegroups.com] On Behalf Of Nishant Pandey Sent: Saturday, June 09, 2012 10:16 PM To: algogeeks@googlegroups.com Subject: Re: [algogeeks] [amazon]: dutch national flag algorithm 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 <algorithm.i...@gmail.com> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com <mailto:algogeeks%2bunsubscr...@googlegroups.com> . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers, Nishant Pandey | Specialist Tools Development | npandey <mailto:gvib...@google.com> @google.com | +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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
