Rotating a vector in time proportional to n using constant space.
— By Yasin
Today I stumbled across an interesting problem which is a small sub-problem for a distributed algorithm I'm currently working on. The concern is that we should rotate a one-dimensional vector of element left by () positions.
For instance, say we have an array with elements should rotate it
by shifts. In example, vector
[1,2,3,4,5,6,7,8] is rotated to
A naive algorithm will use an n-element intermediate vector to do the job in steps or copy the underlying array with language dependant slicing features (where space is ) or compute in-place shift by holding a temporary variable with iterations (which will take a running time of ).
But we are better than this! Can we rotate the vector in time proportional to without additional memory allocations ?
Jon derived a smart insight in which he calls the Aha! moment! Because, in the reverse rotation technique, it is basically two arrays reversed twice. Truly marvelous!
The reversing algorithm is pretty straightforward, and the other two are very clever. But for this code fragment, I will only go through the reversing algorithm because that's the most elegant code. Jon makes use of a bidirectional iterator to perform the task in time.
Now let's dive into the algorithm! Woohoo! 🕺
Recall the example in the problem description. We have to left rotate the vector
by . If we view it as two sub-vectors, we get and items long
In Jon's algorithm, to rotate the vector, we reverse the first sub-vector to
[3,2,1, 4,5,6,7,8]. Essentially, the first reverse of the
is swapping the positions of each element until delta.
Then reverse the second
Sub-vector B to obtain
Like previously, we make use of the two-pointers to swap them in-place
without additional space overhead.
Finally, reverse the whole thing to obtain
That's it! How cool is that, huh?
Here's a Golang implementation of this algorithm. The
reverse function takes a
pointer to the array and bidirectional iterator positions and for swapping
the indexes. Then we loop until to swap
and , and consecutively we increment and decrement
Then comes the real magic. Inside the
reverseRotate function we invoke the
reverse routine times.
The first call is to get (we start from for , and is always ),
and then the second call is to derive (we start from for and swap until ).
At this point, we only need to reverse the entire array once from to
to obtain the rotated vector.
Here's a neat visual playground for you to see the behaviour of this algorithm!
This is an elegant way to solve the problem, especially considering one vector as a sum of two (Prakhar Srivastav, 2014). In Aha! Algorithms research paper Jon mentions that this reversal code is guaranteed time and space-efficient and is so short and damn simple that it's pretty hard to get wrong.
These are some interesting resources I referred while writing this post. Be sure to check these posts from great engineers out there!
- Book - Programming Pearls 2nd Edition
- Paper - Aha! Algorithms
- Prakhar Srivastav @ Google
- Eli Bendersky @ Google
Thanks a million for reading! Until next time!