Rearranging array with O(1) extra memory in faster than O(n^2) time

Go To StackoverFlow.com

3

Suppose I have the following array:

1, 4, 5, 2, 3

I need to rearrange it to

5, 1, 4, 2, 3

There is only on extra space; one int.

I figured one solution to solve it. But it is O(n^2) complexity.

Can anyone offer a faster solution?

Thanks

Edited: sorry, not rotating array.

I need to change original array to result array. The order can be arbitrary. I just need to make A -> B. B is been told to me.

thanks

Edited 2"

Make it clearer. Array B is not fixed. We need to find a general solution for this.

Updated:

Thank you all. Seems like this is a brain teaser question. haha :D

My friend been asked by Amazon interviewer for this. LOL

2012-04-03 23:02
by Anders Lind
What is the transformation there? It's not any kind of sorting that I can see. How do you get from the original to the output? (I understand the space removal, just the ordering I don't. - Corbin 2012-04-03 23:04
Are you rotating the array - Shahbaz 2012-04-03 23:05
As my understanding, need to achieve certain addr store certain value based on requirement - Anders Lind 2012-04-03 23:06
I think you can't get better than O(n^2 - Saeed Amiri 2012-04-03 23:17
Could you be more specific? Can you give an example - Shahbaz 2012-04-03 23:21
If B is known, then there's no work involved, so of course this is O(1) - Oliver Charlesworth 2012-04-03 23:38
Wait a minute, if B is given to you, why do you need to recreate it from A - Shahbaz 2012-04-03 23:45


1

This solution works using O(1) space.

>>> def arrayswap(source, dest):
...     for i in range(len(dest)):
...         source[source.index(dest[i])], source[i] = source[i], source[source.index(dest[i])]
... 
>>> a = [1, 4, 5, 2, 3]
>>> b = [5, 1, 4, 2, 3]
>>> arrayswap(a, b)
>>> a
[5, 1, 4, 2, 3]

Without using python's tuple packing, the value of one of source[i] or source[source.index(dest[i])] could be stored in an int.

2012-04-03 23:48
by fwenom
by source.index(dest[i]) you mean a linear search? That would give O(n^2) performanc - Shahbaz 2012-04-03 23:50
Ah, I didn't read the full problem. Just read the part about O(1) space. Well, at least it is a working solution for others to see and improve. Too bad I can't just do a,b = b,afwenom 2012-04-03 23:51


2

It seems to me that this is just a special case of sorting the array, where the sort order is rather arbitrary. So, an optimal algotithm would have time complexity O(n log n), and using one that does in-place sorting (at the expense of not being a stable sort) would have space complexity O(1). An in-place merge sort would fit the bill, as would an in-place quicksort if average O(n log n) is OK.

2012-04-03 23:21
by mpdonadio
Indeed, O(1) space lets you perform a swap(a,b) operation - ninjagecko 2012-04-03 23:32
@ninjagecko you can even swap(a,b) with O(0) spac - Shahbaz 2012-04-03 23:44
@Shahbaz: I guess that's true, if you have special hardware, or you are not counting registers/memory as space. If you were referring to something else though, I'd love to hear it - ninjagecko 2012-04-03 23:46
@ninjagecko, read up on the xor swapmpdonadio 2012-04-03 23:48
@ninjagecko a = a + b; b = a - b; a = a - b; In general, if $ and # are operators such that a $ b # b = a and a $ b = b $ a (same with #) then you can write a = a$b; b=a#b; a = a#b; One interesting example is xor for both $ and # - Shahbaz 2012-04-03 23:48
@Shahbaz I think you missed ninjagecko's "or you are not counting registers/memory as space" - Daniel Fischer 2012-04-03 23:53
There is no such thing as O(0)Esailija 2012-04-03 23:58
@DanielFischer, in theory (from which the big O notation comes from), you don't think about a and b being loaded in registers. Saying a = a+b does not require extra space. In practice though that's not the case as we all know it - Shahbaz 2012-04-03 23:58
@Esailija, 0 is O(0) because there exists a c > 0 (say 1) where 0 < c*0 for all input sizes n > 0. Note that we are talking about memory, not time - Shahbaz 2012-04-03 23:59
@Shahbaz Typo: 0 <= c*0. As for the space, yes, and I guess ninjagecko's point was the practice, not the theory - Daniel Fischer 2012-04-04 00:04
@DanielFischer, oops, yeah thanks. And of course, once you get down to practice, you have way more memory usage than just a single integer. Think of the function stack frame, CPU cache, instruction register, as well as even the small temporary memories in the ALU performing the arithmetics (if the a = a^b method was used for example) (think of a turing machine to see where that extra memory comes from). Since nobody counts these extra memory, I thought you could skip the data registers also - Shahbaz 2012-04-04 00:09
@Shahbaz I would agree. I just thought that ninjagecko is aware of that too and wanted to relativize (hmm, is that a real word?) the O(0) by a dose of practice. I may be wrong, of course - Daniel Fischer 2012-04-04 00:15
@Shahbaz: ah, cute technique. However I should point out that you are technically using more space, because you are actually storing extra information, or in the case of fixed-sized machine words, bounding the kinds of numbers you can store (numbers whose sum is less than MAXINTSIZE). In the case of fixed-sized machine words, we had spare memory overhead, which you can exploit using this technique, but then one could argue that you are using O(1) memory not in RAM but in the spare bits of the machine word. Still nifty though - ninjagecko 2012-04-04 00:15
@ninjagecko, that's not entirely true. Even if a+b overflows, the underflow from a-b fixes it. After all, addition and subtraction are congruent modulo 2^32 (if 32 bit) and in the end the numbers would be right. Still, that's another reason for people to choose xor to other operators. (P.S. BugFix: in my first comment, a $ b = b $ a (same with #) doesn't need to hold - Shahbaz 2012-04-04 08:39
@Shahbaz: ah, xor, of course, I initially dismissed that for some reason... ingenious! Thank you for enlightening me! = - ninjagecko 2012-04-04 18:45


0

It seems like you are just moving the first three elements to the left (with a wrap around).

So, ignore the index 3 and 4.

  int temp = array[0]
  array[0] = array[1]
  array[1] = array[2]
  array[2] = temp
2012-04-03 23:21
by Justin


-1

You can just do:

temp = arr[0];
arr[0] = arr[2];
arr[2] = arr[4];
arr[4] = arr[1];
arr[1] = arr[3];
arr[3] = temp;

Edit:

To rearrange array a to be as array b, you can just do like this:

for (var i = 0; i < a.length; i++) {
  for (var j = i + 1; a[i] != b [i]; j++) {
    var temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

}

Demo: http://jsfiddle.net/Guffa/5sKdM/

I'm not sure what the big-O is on this one, but with the example data it does 7 comparisons and 2 swaps, so that is definitely better than O(n2).

Also, I'm not sure exactly what counts as an "extra space", so I don't know if this fulfills the requirement of the one extra space, but if it doesn't, neither does the currently accepted answer...

2012-04-03 23:07
by Guffa
If this is indeed the intended answer, that would make it the silliest interview question I heard to date :) :) : - dasblinkenlight 2012-04-03 23:10
sorry, clarified my question. not rotating arra - Anders Lind 2012-04-03 23:10
This is a special case of the code required to implement the PostScript roll command, which takes two arguments - the number of elements from the top of the stack to roll, and the number of positions forward (back) to roll them - DRVic 2012-04-03 23:10
@AndersLind: Updated my answer reflecting your update. : - Guffa 2012-04-04 06:07