Author |
Topic: Rearrange the array numbers (Read 5690 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
Rearrange the array numbers
« on: Mar 15th, 2011, 9:54pm » |
 Quote  Modify
|
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 ?
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
spur
Newbie
Gender:
Posts: 47
|
|
Re: Rearrange the array numbers
« Reply #1 on: Mar 17th, 2011, 12:14pm » |
Quote Modify
|
this can be done with min(#of +ve,# of -ve) extra space easily.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Rearrange the array numbers
« Reply #2 on: Mar 17th, 2011, 2:14pm » |
Quote Modify
|
on Mar 17th, 2011, 12:14pm, 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 ??
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Rearrange the array numbers
« Reply #3 on: Mar 18th, 2011, 9:00am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Rearrange the array numbers
« Reply #4 on: Mar 18th, 2011, 1:35pm » |
Quote Modify
|
@Grimbal: Nice solution. Looks like this is the best we can do.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Rearrange the array numbers
« Reply #5 on: Mar 18th, 2011, 3:32pm » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Rearrange the array numbers
« Reply #6 on: Mar 18th, 2011, 8:54pm » |
Quote Modify
|
@towr: i forgot to count that 
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 ? 
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Rearrange the array numbers
« Reply #7 on: Mar 19th, 2011, 9:23am » |
Quote Modify
|
on Mar 18th, 2011, 3:32pm, 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.
|
| « Last Edit: Mar 19th, 2011, 9:26am by Grimbal » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Rearrange the array numbers
« Reply #8 on: Mar 19th, 2011, 10:51am » |
Quote Modify
|
on Mar 19th, 2011, 9:23am, Grimbal wrote:
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.
|
|
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)
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
harish
Newbie
Gender:
Posts: 11
|
|
Re: Rearrange the array numbers
« Reply #9 on: Apr 9th, 2011, 3:51am » |
Quote Modify
|
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.
|
| « Last Edit: Apr 9th, 2011, 3:52am by harish » |
IP Logged |
|
|
|
singhar
Newbie
Posts: 22
|
|
Re: Rearrange the array numbers
« Reply #10 on: Jul 6th, 2011, 3:37pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Jigsaw
Guest
|
|
Re: Rearrange the array numbers
« Reply #11 on: Jul 7th, 2011, 11:57am » |
Quote Modify
 Remove
|
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.
|
| « Last Edit: Jul 7th, 2011, 9:00pm by jagatsastry » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Rearrange the array numbers
« Reply #12 on: Jul 7th, 2011, 12:45pm » |
Quote Modify
|
That doesn't retain the order among the two groups as required.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dufus
Newbie
Posts: 43
|
|
Re: Rearrange the array numbers
« Reply #13 on: Jan 18th, 2012, 9:26pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Rearrange the array numbers
« Reply #14 on: Jan 19th, 2012, 1:28am » |
Quote Modify
|
It looks like the in-place card shuffling problem. But in reverse.
|
|
IP Logged |
|
|
|
Dufus
Newbie
Posts: 43
|
|
Re: Rearrange the array numbers
« Reply #15 on: Jan 19th, 2012, 2:50am » |
Quote Modify
|
OK.. In that case O(N) time and O(1) space is the best we can do. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print