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

• algorithm

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.

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.

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

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(n²).

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...