Array Rotation & Reversal: The Reversal Trick

Reversing an array flips its order; rotating it shifts every element by k positions, wrapping around the ends. Both are classic interview staples, and the satisfying part is that rotation can be done in place in O(n) time and O(1) space using nothing but reversal — the famous reversal trick. This page builds reversal first, then uses it to rotate.

Reversing in place

Use two pointers, one at each end, swapping and stepping inward until they meet. Each element is touched once.

#include <vector>
#include <algorithm>
void reverse(std::vector<int>& a, int lo, int hi) {
    while (lo < hi) std::swap(a[lo++], a[hi--]);
}
// reverse whole array: reverse(a, 0, a.size() - 1);

void reverse(int[] a, int lo, int hi) {
    while (lo < hi) {
        int tmp = a[lo]; a[lo] = a[hi]; a[hi] = tmp;
        lo++; hi--;
    }
}
// reverse whole array: reverse(a, 0, a.length - 1);

function reverse(a, lo, hi) {
  while (lo < hi) {
    [a[lo], a[hi]] = [a[hi], a[lo]];
    lo++; hi--;
  }
}
// reverse whole array: reverse(a, 0, a.length - 1);

def reverse(a, lo, hi):
    while lo < hi:
        a[lo], a[hi] = a[hi], a[lo]
        lo += 1
        hi -= 1
# reverse whole array: reverse(a, 0, len(a) - 1)

Complexity: O(n) time, O(1) extra space.

The reversal trick for rotation

To rotate an array left by k, observe that the answer is just the array split at index k with the two pieces swapped. You can achieve that swap with three reversals:

Reverse the first k elements.
Reverse the remaining n - k elements.
Reverse the whole array.

For [1,2,3,4,5] with k = 2: reverse front → [2,1,3,4,5], reverse back → [2,1,5,4,3], reverse all → [3,4,5,1,2]. Done.

Always reduce k modulo n first, so rotating by more than the length (or by a negative) still works.

void rotateLeft(std::vector<int>& a, int k) {
    int n = a.size();
    if (n == 0) return;
    k %= n; if (k < 0) k += n;
    reverse(a, 0, k - 1);
    reverse(a, k, n - 1);
    reverse(a, 0, n - 1);
}

void rotateLeft(int[] a, int k) {
    int n = a.length;
    if (n == 0) return;
    k %= n; if (k < 0) k += n;
    reverse(a, 0, k - 1);
    reverse(a, k, n - 1);
    reverse(a, 0, n - 1);
}

function rotateLeft(a, k) {
  const n = a.length;
  if (n === 0) return;
  k %= n; if (k < 0) k += n;
  reverse(a, 0, k - 1);
  reverse(a, k, n - 1);
  reverse(a, 0, n - 1);
}

def rotate_left(a, k):
    n = len(a)
    if n == 0:
        return
    k %= n
    reverse(a, 0, k - 1)
    reverse(a, k, n - 1)
    reverse(a, 0, n - 1)

Complexity: O(n) time, O(1) space — each of the three reversals is linear.

Tip: To rotate right by k instead of left, rotate left by n - k (after taking k %= n). Or reorder the reversals: reverse the whole array first, then the first k, then the rest.

Why not just use a temporary array?

You can rotate by copying into a new array at shifted positions — also O(n) time, but O(n) extra space. The reversal trick matches the time and beats the space, which is why interviewers love it.

// O(n) time, O(n) space alternative
std::vector<int> rotateCopy(const std::vector<int>& a, int k) {
    int n = a.size();
    std::vector<int> out(n);
    k %= n; if (k < 0) k += n;
    for (int i = 0; i < n; i++) out[i] = a[(i + k) % n];
    return out;
}

// O(n) time, O(n) space alternative
int[] rotateCopy(int[] a, int k) {
    int n = a.length;
    int[] out = new int[n];
    k %= n; if (k < 0) k += n;
    for (int i = 0; i < n; i++) out[i] = a[(i + k) % n];
    return out;
}

// O(n) time, O(n) space alternative
function rotateCopy(a, k) {
  const n = a.length;
  const out = new Array(n);
  k %= n; if (k < 0) k += n;
  for (let i = 0; i < n; i++) out[i] = a[(i + k) % n];
  return out;
}

# O(n) time, O(n) space alternative
def rotate_copy(a, k):
    n = len(a)
    k %= n
    return [a[(i + k) % n] for i in range(n)]

For beginners: Built-in shortcuts exist (Python’s collections.deque.rotate, slicing a[k:] + a[:k]), but learn the reversal trick — it teaches the in-place mindset you’ll reuse for many array problems.

Where this shows up

Rotation appears in circular buffers, scheduling, and string rotation checks (a string is a rotation of another iff it’s a substring of the doubled string — see string manipulation). Practice these patterns on the array exercises, then move on to strings.