Rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space

Question

The task is to rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space.

Example:

2 1 3 5 4 0 

becomes:

3 1 5 0 4 2

I can think of an O(n²) solution. An O(n) solution was presented here:

1. Increase every array element arr[i] by (arr[arr[i]] % n)*n.
2. Divide every element by n.

But this is very limited as it will cause buffer overflow.

Can anyone come up with an improvement upon this?

Answer 1

If the values in the array are all positive (or all negative), one way to avoid overflow could be to run the permutation cycles and use the integer sign to mark visited indexes. (Alternatively, if the array length is smaller than 2^(number of bits for one array element - 1), rather than use the sign, we could shift all the values one bit to the left and use the first bit to mark visited indexes.) This algorithm results in both less iterations and less modifications of the original array values during run-time than the algorithm you are asking to improve.

JSFiddle: http://jsfiddle.net/alhambra1/ar6X6/

JavaScript code:

function rearrange(arr){
    var visited = 0,tmp,indexes,zeroTo

    function cycle(startIx){
        tmp = {start: startIx, value: arr[startIx]}
        indexes = {from: arr[startIx], to: startIx}

        while (indexes.from != tmp.start){
            if (arr[indexes.from] == 0)
                zeroTo = indexes.to
            if (indexes.to == visited){
                visited++
                arr[indexes.to] = arr[indexes.from]
            } else {
                arr[indexes.to] = -arr[indexes.from]
            }
            indexes.to = indexes.from
            if (indexes.from != tmp.start)
                indexes.from = arr[indexes.from]
        }

        if (indexes.to == visited){
            visited++
            arr[indexes.to] = tmp.value
        } else {
            arr[indexes.to] = -tmp.value
        }
    }

    while (visited < arr.length - 1){
        cycle(visited)

        while (arr[visited] < 0 || visited == zeroTo){
            arr[visited] = -arr[visited]
            visited++
        }
    }

    return arr
}