Data Structures · Array

Rotate an Array

The idea

Picture people seated around the last row of a cinema playing musical chairs to the right. Everyone shifts one seat over — but the person in the last seat would fall off the row. So they stand up first, everyone slides across, and the stander takes the now-empty first seat.

The problem

Rotate the array one position to the right: every element moves one slot over, and the last element wraps around to the front. Done naively you overwrite a value before it has been copied — so the whole trick is saving the wrap-around element BEFORE the shift, then writing it into the freed front slot.

Why it's slow

Every element changes position, so n writes is the floor — this shift does exactly that plus one saved value. The classic interview twist is rotating by k positions: repeating this n·k times is the slow answer; the expected one rotates in one pass using the three-reversal trick, built directly on the Reverse an Array lesson.

Pseudocode

  1. remember the last element — it will wrap around
    Explain this line

    The last element is the only one that would be overwritten with nowhere to go — stash it first.

  2. walk from the back toward the front
    Explain this line

    Shifting must go back-to-front: front-to-back would overwrite values before they are copied.

  3. copy each element one slot to the right
    Explain this line

    Each copy frees the slot to its left for the next copy — a chain of dominoes falling rightward.

  4. place the remembered element into the front slot
    Explain this line

    The front slot has been vacated by the shift; the stashed value completes the circle.

  5. every element has moved one step around the circle
    Explain this line

    One full rotation: what was last is now first, everything else moved one right.

Complexity

Best Average Worst Space
O(n) O(n) O(n) O(1)

n writes and one saved element per single rotation. Rotating by k: repeat = O(n·k); the three-reversal trick keeps it O(n) with O(1) space.

Code

python 
def rotate_right_once(a):
    if not a:
        return a
    last = a[-1]
    for i in range(len(a) - 2, -1, -1):
        a[i + 1] = a[i]
    a[0] = last
    return a
java 
static void rotateRightOnce(int[] a) {
    if (a.length == 0) return;
    int last = a[a.length - 1];
    for (int i = a.length - 2; i >= 0; i--) {
        a[i + 1] = a[i];
    }
    a[0] = last;
}
cpp 
void rotateRightOnce(std::vector<int>& a) {
    if (a.empty()) return;
    int last = a.back();
    for (int i = (int)a.size() - 2; i >= 0; --i) {
        a[i + 1] = a[i];
    }
    a[0] = last;
}
javascript 
function rotateRightOnce(a) {
  if (a.length === 0) return a;
  const last = a[a.length - 1];
  for (let i = a.length - 2; i >= 0; i--) {
    a[i + 1] = a[i];
  }
  a[0] = last;
  return a;
}
dart 
void rotateRightOnce(List<int> a) {
  if (a.isEmpty) return;
  final last = a.last;
  for (var i = a.length - 2; i >= 0; i--) {
    a[i + 1] = a[i];
  }
  a[0] = last;
}

Quick check