</>EmbeddedInterview

How do you rotate an array by d positions?

MediumArrays & Strings (Coding Round)

Short answer: Use the reversal algorithm. To rotate left by d: reverse the first d elements, reverse the rest, then reverse the whole array. It runs in O(n) time with O(1) extra memory. Reduce d with d %= n first.

#include <stddef.h>

static void reverse_range(int *a, size_t lo, size_t hi)   /* inclusive */
{
    while (lo < hi) {
        int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
        lo++; hi--;
    }
}

void rotate_left(int *a, size_t n, size_t d)
{
    if (n == 0) return;
    d %= n;
    if (d == 0) return;
    reverse_range(a, 0, d - 1);
    reverse_range(a, d, n - 1);
    reverse_range(a, 0, n - 1);
}
/* {1, 2, 3, 4, 5, 6}, d = 2 -> {3, 4, 5, 6, 1, 2} */

Dry run (d = 2):

start          1 2 | 3 4 5 6
reverse [0,1]  2 1 | 3 4 5 6
reverse [2,5]  2 1 | 6 5 4 3
reverse all    3 4 5 6 1 2

Why it works: write the array as A B where A is the first d elements. We want B A. Reversing each part gives Aʳ Bʳ, and reversing the whole thing gives (Aʳ Bʳ)ʳ = B A.

Right rotation by d is left rotation by n - d, or reverse the whole array first and then the two parts.

Other methods

Method Time Extra space
Rotate by one, d times O(n·d) O(1)
Copy to a temp array O(n) O(n) or O(d)
Juggling (GCD cycles) O(n) O(1)
Reversal O(n) O(1)

Forgetting d %= n is the usual bug: with d = 8 and n = 6, reverse_range(a, 0, 7) writes past the array.

Embedded relevance: the same idea rotates a circular log buffer into chronological order before sending it, without a second buffer.