Saturday, July 6, 2013

Array Rotation By A Particular Amount

John Bentley's "Programming Pearls" again, with the rotated array problem.  So we have a one-dimensional array of N elements that we have to rotate left by I positions. We have to do this in time proportional to N and in O(1) space. So for example if we have the array [1 2 3 4 5 6 7 8 9] and we want to rotate it by 3 positions we should result in this array: [4 5 6 7 8 9 1 2 3]. Note that the array is not necessarily sorted.

There's plenty of solutions that may come in our minds at first but they probably require additional temporary space. For example we could copy the I elements into a temporary vector, then move to the left all the rest in the original array by I positions and finally copy the elements from the temporary array to the end of the original array. As you see this is too expensive space wise.

To solve this problem we will require a different view of the problem and some time until you hit that aha! moment. We basically need to transform AB to BA, where A and B are sub-arrays of the original array. Imagine we have a routine that can reverse the elements in a specific portion of the original array (A, B). So we reverse elements in A first resulting in ARB and then reverse the elements in B resulting in ARBR. And finally we need to reverse ARBR to produce (ARBR)R which is in fact the array that we were looking for BA.

This may be easier to understand with an example. So we have our array arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] that we need to rotate left by 3. We need to first rotate the sub-array [1, 2, 3] resulting in [3, 2, 1, 4, 5, 6, 7, 8, 9] and then we rotate [4, 5, 6, 7, 8, 9] resulting in [3, 2, 1, 9, 8, 7, 6, 5, 4]. And finally we reverse the whole array resulting in [4, 5, 6, 7, 8, 9, 1, 2, 3] which is the array we were looking for.

In code it looks even easier to understand, considering that we already have the routine that does the reversal of the elements in an array:

The routine for reversing is just a for loop that is of O(n/2) complexity, where n is the number of elements it has to reverse. The routine may look like this:

- the swap routine is trivial and may look like this:

No comments:

Post a Comment