Write a program to cyclically rotate an array by one

The problem, simply

You get an array. Rotate it one step to the right, in a circle: the last item moves to the front, and every other item moves one place to the right.

Change the array itself, using only a little extra room.

A story to remember it

Picture it

Examples

Way 1: the simple way

Build a new array. Put the last item at index 0, then copy the old item i - 1 into new spot i. Copy it back if the caller expects the same array.

class Solution {
    public void rotate(int[] arr) {
        int n = arr.length;
        if (n <= 1) return;
        int[] out = new int[n];
        out[0] = arr[n - 1];                  // the last item goes first
        for (int i = 1; i < n; i++) out[i] = arr[i - 1];
        System.arraycopy(out, 0, arr, 0, n);  // put the result back
    }
}

How long it takes: one walk to fill and one to copy back, O(n). Extra room: a second array, O(n).

Way 2: the clever way

Hold one item, then slide from the back.

1. Save the last item in last.
2. For i from n - 1 down to 1, copy arr[i - 1] into arr[i].
3. Put last into arr[0].

Going from the back matters. Each copy writes into a spot whose old value was already moved or saved.

class Solution {
    public void rotate(int[] arr) {
        int n = arr.length;
        if (n <= 1) return;               // nothing to rotate
        int last = arr[n - 1];            // hold on to the last item
        for (int i = n - 1; i > 0; i--) {
            arr[i] = arr[i - 1];          // slide right, from the back
        }
        arr[0] = last;                    // the saved item goes in front
    }
}

How long it takes: one walk, O(n). Extra room: one saved number, O(1).

Watch out for

• Read the direction carefully. "Rotate by one" usually means to the right (the last item goes first). Rotating left means the first item goes last: save arr[0] and slide from the front.
• An empty array has no arr[n - 1]. Return early when n <= 1.

What interviewers ask next

• Rotate by k steps. Doing one step k times is O(n k). Instead use three flips: flip the whole array, then flip the first k items, then flip the rest. That is O(n) time and O(1) room. Use k % n first.
• Why do three flips work? Flipping the whole array puts the last k items in front, but backwards, and the rest after them, also backwards. Flipping each part fixes their inside order.
• Another O(n) and O(1) method is the juggling method: move items in cycles of step k, and there are gcd(n, k) cycles.
• Rotate a linked list by k. Join the tail to the head to make a ring, walk to the new tail, and cut there.

Remember this

Grown-up words: the merry-go-round turn is a cyclic rotation, sliding from the back avoids overwriting values, and the three flips for k steps are the reversal algorithm.