# Vector Rotation

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 $n$ element left by $d$ ($\Delta$) positions.

# Problem Statement

For instance, say we have an array with $n=8$ elements should rotate it
by $d=3$ shifts. In example, vector `[1,2,3,4,5,6,7,8]`

is rotated to `[4,5,6,7,8,1,2,3]`

.

A naive algorithm will use an n-element intermediate vector to do the job in $n$ steps
or copy the underlying array with language dependant slicing features (where space is $O(n)$)
or compute **in-place** shift by holding a temporary variable with $d$ iterations (which
will take a running time of $O(\Delta * n)$).

But we are better than this! Can we rotate the vector in time proportional to $O(n)$ without additional memory allocations $O(1)$?

# Aha!

Yes, we can! Thanks to Jon Bentley, In his
Programming Pearls (2nd Edition)
book, he mentioned three vector rotation algorithms called
**Juggling**, **Swapping**, and **Reversing**.

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 $O(n)$ time.

Now let's dive into the algorithm! Woohoo! 🕺

# Reverse Rotate

Recall the example in the problem description. We have to *left* rotate the vector `[1,2,3,4,5,6,7,8]`

by $3$. If we view it as two sub-vectors, we get $3$ and $5$ items long
sub-vector: `[1,2,3]`

-`[4,5,6,7,8]`

.

In Jon's algorithm, to rotate the vector, we reverse the first sub-vector to
obtain `[3,2,1, 4,5,6,7,8]`

. Essentially, the first reverse of the `Sub-vector A`

is swapping the positions of each element until delta.

Then reverse the second `Sub-vector B`

to obtain `[3,2,1, 8,7,6,5,4]`

.
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 `[4,5,6,7,8,1,2,3]`

.

That's it! How cool is that, huh?

# Implementation

Here's a Golang implementation of this algorithm. The `reverse`

function takes a
pointer to the array $x$ and *bidirectional iterator* positions $i$ and $j$ for swapping
the indexes. Then we loop $\sum_{i}^{j}$ until $i \lt j$ to swap
$x_i$ and $x_j$, and consecutively we increment $i$ and decrement
$j$ by one.

Then comes the real magic. Inside the `reverseRotate`

function we invoke the `reverse`

routine $3$ times.
The first call is to get $A'$ (we start from $0$ for $i$, and $j$ is always $\lt\Delta$),
and then the second call is to derive $B'$ (we start from $\Delta$ for $i$ and swap until $n-1$).
At this point, we only need to reverse the entire array once from $0$ to $n - 1$
to obtain the rotated vector.

# Interactive Example

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.

It is precisely the code
that Brian Kernighan &
Bill Plauger use
in their Software Tools
book's editor
and also what Ken Thompson used in
his text editor `ed`

to manipulate lines.

# Stay Curious

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!Published —