Rotate Array

NeetCode: Rotate Array · LeetCode: 189. Rotate Array · Difficulty: Medium

Given an integer array nums, rotate it to the right by k steps, where k is non-negative. Modify the array in place. k may be larger than the length of the array.

Example

Text

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

Brute force: rotate by one, k times

One rotation by one step moves the last element to the front and shifts everything else right. Doing it k times gives the answer. Rotating by n steps returns to the start, so first reduce k to k % n (and guard the empty array, where % 0 throws ArithmeticException).

Java

import java.util.Arrays;

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

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

Output

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

Time: O(n · k), which is O(n^2) when k is close to n. Space: O(1).

Better: copy into an extra array

The element at index i must end up at index (i + k) % n. Write each element straight to its final slot in a new array, then copy the result back with System.arraycopy. The index i + k is added in long so it cannot wrap around in int when k is large. It is linear but uses O(n) extra memory.

Java

import java.util.Arrays;

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

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

Output

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

Time: O(n). Space: O(n).

Optimal: three reversals

Rotating right by k moves the last k elements to the front while keeping the order inside both parts. Reversing does exactly that in three steps:

Reverse the whole array: [1,2,3,4,5,6,7] becomes [7,6,5,4,3,2,1].
Reverse the first k elements: [5,6,7,4,3,2,1].
Reverse the remaining n - k elements: [5,6,7,1,2,3,4].

Each element is touched a constant number of times and no extra array is needed. Reduce k with k % n first so that k >= n works and the index k - 1 stays in range. When k % n is 0, the call reverse(nums, 0, -1) does nothing because lo < hi is false. The helper reverse takes inclusive bounds.

Java

import java.util.Arrays;

class Solution {
    public 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);
    }

    // Reverses nums[lo..hi] (both ends inclusive).
    private void reverse(int[] nums, int lo, int hi) {
        while (lo < hi) {
            int tmp = nums[lo];
            nums[lo] = nums[hi];
            nums[hi] = tmp;
            lo++;
            hi--;
        }
    }
}

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

Output

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

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

For a List, Collections.rotate(list, k) performs the same rotation to the right. int[] has no built-in rotate.