Rotate Array

Given an integer array nums, rotate it to the right by k steps, in place. This is LeetCode 189.

Example 1
Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: [5, 6, 7, 1, 2, 3, 4]
Example 2
Input: nums = [-1, -100, 3, 99], k = 2
Output: [3, 99, -1, -100]

How to Think About It

Step 1: Simple ways

  • Move every element one step, k times: O(n × k).
  • Copy into a new array at index (i + k) % n: O(n) time but O(n) extra space.

Step 2: k larger than n

Rotating by n puts every element back where it started, so only k % n matters.

Step 3: Three reversals

Rotating right by k moves the last k elements to the front, keeping each part's order. Reversals do this in place:

  1. Reverse the whole array: the last k elements are now at the front, but backwards.
  2. Reverse the first k elements: they are now in the right order.
  3. Reverse the remaining n - k elements: they are in the right order too.

Walkthrough

nums = [1, 2, 3, 4, 5, 6, 7], k = 3.

StepArray after
reverse all[7, 6, 5, 4, 3, 2, 1]
reverse the first 3[5, 6, 7, 4, 3, 2, 1]
reverse the last 4[5, 6, 7, 1, 2, 3, 4]

Java Solution

The reverse helper is the swap loop from Reverse String, applied to a range.

Java
import java.util.Arrays;

public class RotateArray {

    public static void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;                               // rotating by n changes nothing
        reverse(nums, 0, n - 1);              // 1. reverse everything
        reverse(nums, 0, k - 1);              // 2. reverse the first k
        reverse(nums, k, n - 1);              // 3. reverse the rest
    }

    private static void reverse(int[] a, int lo, int hi) {
        while (lo < hi) {
            int tmp = a[lo];
            a[lo++] = a[hi];
            a[hi--] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6, 7};
        rotate(a, 3);
        System.out.println(Arrays.toString(a));   // [5, 6, 7, 1, 2, 3, 4]
        int[] b = {-1, -100, 3, 99};
        rotate(b, 2);
        System.out.println(Arrays.toString(b));   // [3, 99, -1, -100]
    }
}

The original implementation, RotateArray.java, is on GitHub.

Complexity

  • Time: O(n): each element is swapped about twice.
  • Space: O(1).

The same reversal trick rotates a string or a list of words.