Rotate Array

Given an array nums and a non-negative integer k, rotate the array to the right by k positions: every element moves k places right, and elements that fall off the end wrap around to the front. Do it in place.

LeetCode: 189. Rotate Array

Example 1

Text

Input:  nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: [5, 6, 7, 1, 2, 3, 4]
Explanation:
  rotate 1: [7, 1, 2, 3, 4, 5, 6]
  rotate 2: [6, 7, 1, 2, 3, 4, 5]
  rotate 3: [5, 6, 7, 1, 2, 3, 4]

Example 2

Text

Input:  nums = [-1, -100, 3, 99], k = 6
Output: [3, 99, -1, -100]
Explanation: rotating 4 positions gives back the original array, so k = 6 is the same as k = 2.

In every approach, reduce k first with k % n, since rotating by n changes nothing.

Brute force: rotate by one, k times

A rotation by one saves the last element, shifts everything else one place right, and puts the saved element at index 0. Repeat k times.

Java

import java.util.Arrays;

public class Main {
    static void rotate(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) {
            return;
        }
        for (int step = 0; step < k % n; step++) {
            int last = nums[n - 1];
            for (int i = n - 1; i >= 1; i--) {
                nums[i] = nums[i - 1];
            }
            nums[0] = last;
        }
    }

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

Output

[5, 6, 7, 1, 2, 3, 4] [3, 99, -1, -100]

Time: O(n·k). Space: O(1).

Better: copy into a new array

Element i belongs at position (i + k) % n. Write each element to its new position in a copy, then copy back.

Java

import java.util.Arrays;

public class Main {
    static void rotate(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) {
            return;
        }
        int[] rotated = new int[n];
        for (int i = 0; i < n; i++) {
            rotated[(i + k) % n] = nums[i];
        }
        System.arraycopy(rotated, 0, nums, 0, n);
    }

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

Output

[5, 6, 7, 1, 2, 3, 4]

Time: O(n). Space: O(n) for the copy. i + k is an int sum, so it can overflow when k is close to Integer.MAX_VALUE. Reduce k with k % n first.

Optimal: three reversals

Rotating right by k moves the last k elements to the front, keeping the order inside each part. Reversing the whole array puts those k elements first, but each part is now backwards. Reversing each part again fixes that.

Walkthrough with [1, 2, 3, 4, 5, 6, 7], k = 3:

step	array
start	`[1, 2, 3, 4, 5, 6, 7]`
reverse all	`[7, 6, 5, 4, 3, 2, 1]`
reverse first k = 3	`[5, 6, 7, 4, 3, 2, 1]`
reverse the remaining 4	`[5, 6, 7, 1, 2, 3, 4]`

Java has no built-in reverse for a range of an int[], so a helper reverse(nums, from, to) swaps elements from both ends of the inclusive range [from, to].

Java

import java.util.Arrays;

public class Main {
    static void reverse(int[] nums, int from, int to) { // inclusive range
        while (from < to) {
            int tmp = nums[from];
            nums[from] = nums[to];
            nums[to] = tmp;
            from++;
            to--;
        }
    }

    static void rotate(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) {
            return;
        }
        k = k % n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

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

Output

[5, 6, 7, 1, 2, 3, 4] [3, 99, -1, -100]

Time: O(n): each element is swapped at most twice. Space: O(1).

When k is 0, reverse(nums, 0, -1) does nothing, because from < to is false.

In real code

Collections.rotate(list, distance) rotates a List to the right by distance positions in place. It reduces the distance modulo the list size itself, so any non-negative or negative distance is safe, and an empty list does nothing.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6, 7));
        Collections.rotate(nums, 3);
        System.out.println(nums);
        Collections.rotate(nums, -3); // a negative distance rotates left
        System.out.println(nums);
    }
}

Output

[5, 6, 7, 1, 2, 3, 4]
[1, 2, 3, 4, 5, 6, 7]

Edge cases

Empty array: nothing to do (and k % 0 would throw ArithmeticException, hence the early return).
k is a multiple of n: the array is unchanged.
k larger than n: reduced by k % n.
Rotate left by k: the same as rotating right by n - k % n.