Check this out, it works in O(n); int i = 0; int j = n-1;
while((i<n && j>= 0)&&(i<j)) { if(a[i]>0 && a[j]<0) { swap(a[i],a[j]); i++; j--; } else { if(a[i]<0) i++; if(a[j]>0) j--; } } Thanks, Mani On Thu, Jun 14, 2012 at 1:05 PM, Mad Coder <imamadco...@gmail.com> wrote: > > As nothing is written about space complexity, I am assuming that we can > take extra space. > > Take a temporary array of length n. > > 1. Maintain a counter for the length of temporary array filled till now. > > 2. Traverse the given array. If value contained is negative insert it in > new array and update counter. After complete traversal all negative values > will be in the temporary array. > > 3. Traverse again the given array. Repeat step 2 but this time for > positive numbers. > > Finally temporary array contains the required answer. If required copy it > into original array. > > As this approach takes max. 3 traversals so its complexity is O(n). > > -- > 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. > -- Thanks & Regards, Mani http://www.sanidapa.com - The music Search engine -- 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.