wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Rearrange the array numbers
        
(Message started by: birbal on Mar 15^th, 2011, 9:54pm)

Title: Rearrange the array numbers
Post by birbal on Mar 15^th, 2011, 9:54pm

Given an array of +ve and -ve integers, re-arrange it so that u have +ves on one end and -ves on other, but we have to retain the order of appearance.

for eg,
1,7,-5,9,-12,15
ans=
-5,-12,1,7,9,15

is it possible to do it in O(n) without using extra space ?

Title: Re: Rearrange the array numbers
Post by spur on Mar 17^th, 2011, 12:14pm

this can be done with min(#of +ve,# of -ve) extra space easily.

Title: Re: Rearrange the array numbers
Post by birbal on Mar 17^th, 2011, 2:14pm

on 03/17/11 at 12:14:58, spur wrote:

this can be done with min(#of +ve,# of -ve) extra space easily.

In the worst case, that can be of O(n). Any ideas to do it without extra space ??

Title: Re: Rearrange the array numbers
Post by Grimbal on Mar 18^th, 2011, 9:00am

The best I can think of is:

- split the array in 2 regions
- apply the algorithm on each half
you get negative - positive - negative - positive
- swap the 2 middle parts

That should do it in O(n log n).
At least we have a working algorithm with O(1) extra space.

Title: Re: Rearrange the array numbers
Post by birbal on Mar 18^th, 2011, 1:35pm

@Grimbal: Nice solution. Looks like this is the best we can do.

Title: Re: Rearrange the array numbers
Post by towr on Mar 18^th, 2011, 3:32pm

Don't you need O(log n) extra space to make that work? You need to keep track of a stack of halves and halves of halves etc.

Title: Re: Rearrange the array numbers
Post by birbal on Mar 18^th, 2011, 8:54pm

@towr: i forgot to count that ;D

Perhaps we can do it iteratively by grouping the elements in smaller groups and then swapping the elements to form larger groups with same property.

(1,7),(-5,9),(-12,15) - groups of two
(-5,1,7,9),(-12,15) - groups of 4 (except the last one)
(-5,-12,1,7,9,15) - final result.

it may happen that we have to swap p positive numbers with n negative numbers. for that we can swap in chunks of gcd(p,n) to make it work in O(p+n)
Overall it will be O(n log n). Any comments ? 8)

Title: Re: Rearrange the array numbers
Post by Grimbal on Mar 19^th, 2011, 9:23am

on 03/18/11 at 15:32:00, towr wrote:

Don't you need O(log n) extra space to make that work? You need to keep track of a stack of halves and halves of halves etc.

Right. A common mistake.

Well, you could do the same work in a non-recursive way, sort all 2-arrays, then merge them to 4-arrays, then 8-arrays, with special care when you reach the end of the array. That would not require this O(log n) space to keep track.

But that makes the algorithm uglier. In real life I wouldn't do that to save O(log n) space.

A better way would be do the same but aligning on the existing positive and negative regions:
Split the array in negative and positive regions, with possibly a zero-sized negative region at the beginning and a zero-sized positive region at the end.
Process them 4 by 4 (i.e. groups of negative-positive-negative-positive) by swapping the 2 center regions. Proceed to the end of the array.
Restart the scan from the start until there is nothing to swap.
One pass would be O(n) and you will need max O(log n) passes.

That should be O(n log n) with O(1) space.

Title: Re: Rearrange the array numbers
Post by birbal on Mar 19^th, 2011, 10:51am

on 03/19/11 at 09:23:40, Grimbal wrote:

Yes this approach is even better. And on a average case, it would be even less than O(n log n). Worst case would be O(n log n)

Title: Re: Rearrange the array numbers
Post by harish on Apr 9^th, 2011, 3:51am

If we partition the array using the pivot value as 0, it should work fine.

As quick sort sorts in-place, this should also retain the relative positions of the numbers.

Title: Re: Rearrange the array numbers
Post by singhar on Jul 6^th, 2011, 3:37pm

We follow the merge-sort approach but dont actually merge the sub-arrays. Instead, we rotate the sub-array consisting of the -ve and +ve numbers so that the -ves and the +ves are together.

e.g. | k -ves | (n-k) +ves | t -ves | (n-t) +ves

so the sub-array in the middle consisting of the | (n-k) +ves | t -ves | should be simply rotated by t to get the -ves all in place. This rotation is instead of actual merge.

And we can do the rotations in O(n) time in place.

Title: Re: Rearrange the array numbers
Post by Jigsaw on Jul 7^th, 2011, 11:57am

This can be done in two passes with constant space.

i=0, j=Arr.length - 1;
while(true)
{
while i < len
Move i from left to right. Stop when you find a -ve number.

while j>=0
Move j from right to left. Stop when you find a +ve number.

Swap Arr[i], Arr[j]
if(i == len-1 || j==0) break
}

reverse(Arr);

Edit: This works only when the number of -ve and +ve numbers are equal. Also, the order of the groups wouldn't be preserved.

Title: Re: Rearrange the array numbers
Post by towr on Jul 7^th, 2011, 12:45pm

That doesn't retain the order among the two groups as required.

Title: Re: Rearrange the array numbers
Post by Dufus on Jan 18^th, 2012, 9:26pm

Sometimes back I encountered a special case of this problem.

where negative and positive integers are strictly alternating.
Ex : 1 -2 3 -4 5 -6
i.e. given such an alternating sequence of positive and negative numbers we need to arrange them so that positive numbers are in the beginning with their original order retained followed by all negative numbers with their original order retained.

So the output to input given above should be: 1 3 5 -2 -4 -6.

I think this problem is doable in O(N) time and O(1) space but the problem poser insisted on using no extra space. Any thoughts?

Title: Re: Rearrange the array numbers
Post by Grimbal on Jan 19^th, 2012, 1:28am

It looks like the in-place card shuffling problem. But in reverse.

Title: Re: Rearrange the array numbers
Post by Dufus on Jan 19^th, 2012, 2:50am

OK.. In that case O(N) time and O(1) space is the best we can do. :)