189. Rotate Array - Explanation

Description

You are given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7,8], k = 4

Output: [5,6,7,8,1,2,3,4]

Explanation:
rotate 1 steps to the right: [8,1,2,3,4,5,6,7]
rotate 2 steps to the right: [7,8,1,2,3,4,5,6]
rotate 3 steps to the right: [6,7,8,1,2,3,4,5]
rotate 4 steps to the right: [5,6,7,8,1,2,3,4]

Example 2:

Input: nums = [1000,2,4,-3], k = 2

Output: [4,-3,1000,2]

Explanation:
rotate 1 steps to the right: [-3,1000,2,4]
rotate 2 steps to the right: [4,-3,1000,2]

Constraints:

1 <= nums.length <= 100,000
-(2^31) <= nums[i] <= ((2^31)-1)
0 <= k <= 100,000

Follow up: Could you do it in-place with O(1) extra space?

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Array Manipulation - Understanding how to modify arrays in-place by swapping and shifting elements
Modular Arithmetic - Using the modulo operator to handle rotation amounts larger than array length
Array Reversal - The technique of reversing a subarray in-place using two pointers
Cyclic Traversal - Following cycles in an array where each element points to its destination position

1. Brute Force

Intuition

The simplest way to rotate an array by k positions is to perform k single rotations. In each rotation, we save the last element, shift every element one position to the right, and place the saved element at the front. This mimics the physical act of rotating items in a line. While straightforward, this approach is slow because we repeat the entire shift process k times.

Algorithm

Compute k = k % n to handle cases where k is larger than the array length.
Repeat k times:
- Store the last element in a temporary variable.
- Shift all elements one position to the right.
- Place the saved element at index 0.

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n
        while k:
            tmp = nums[n - 1]
            for i in range(n - 1, 0, -1):
                nums[i] = nums[i - 1]
            nums[0] = tmp
            k -= 1

public class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        while (k > 0) {
            int tmp = nums[n - 1];
            for (int i = n - 1; i > 0; i--) {
                nums[i] = nums[i - 1];
            }
            nums[0] = tmp;
            k--;
        }
    }
}

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        while (k > 0) {
            int tmp = nums[n - 1];
            for (int i = n - 1; i > 0; i--) {
                nums[i] = nums[i - 1];
            }
            nums[0] = tmp;
            k--;
        }
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {void} Do not return anything, modify nums in-place instead.
     */
    rotate(nums, k) {
        const n = nums.length;
        k %= n;
        while (k > 0) {
            const tmp = nums[n - 1];
            for (let i = n - 1; i > 0; i--) {
                nums[i] = nums[i - 1];
            }
            nums[0] = tmp;
            k--;
        }
    }
}

public class Solution {
    public void Rotate(int[] nums, int k) {
        int n = nums.Length;
        k %= n;

        while (k > 0) {
            int tmp = nums[n - 1];
            for (int i = n - 1; i > 0; i--) {
                nums[i] = nums[i - 1];
            }
            nums[0] = tmp;
            k--;
        }
    }
}

func rotate(nums []int, k int) {
    n := len(nums)
    k %= n
    for k > 0 {
        tmp := nums[n-1]
        for i := n - 1; i > 0; i-- {
            nums[i] = nums[i-1]
        }
        nums[0] = tmp
        k--
    }
}

class Solution {
    fun rotate(nums: IntArray, k: Int) {
        val n = nums.size
        var rotations = k % n
        while (rotations > 0) {
            val tmp = nums[n - 1]
            for (i in n - 1 downTo 1) {
                nums[i] = nums[i - 1]
            }
            nums[0] = tmp
            rotations--
        }
    }
}

class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        let n = nums.count
        var rotations = k % n
        while rotations > 0 {
            let tmp = nums[n - 1]
            for i in stride(from: n - 1, to: 0, by: -1) {
                nums[i] = nums[i - 1]
            }
            nums[0] = tmp
            rotations -= 1
        }
    }
}

Time & Space Complexity

Time complexity: $O(n * k)$
Space complexity: $O(1)$ extra space.

2. Extra Space

Intuition

Instead of repeatedly shifting elements, we can directly compute the final position of each element. If an element is at index i, after rotation it will be at index (i + k) % n. By using a temporary array to store the rotated result, we can place each element in its correct position in a single pass, then copy everything back.

Algorithm

Create a temporary array tmp of the same size as nums.
For each index i, place nums[i] at position (i + k) % n in tmp.
Copy all elements from tmp back into nums.

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        tmp = [0] * n
        for i in range(n):
            tmp[(i + k) % n] = nums[i]

        nums[:] = tmp

public class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] tmp = new int[n];
        for (int i = 0; i < n; i++) {
            tmp[(i + k) % n] = nums[i];
        }
        for (int i = 0; i < n; i++) {
            nums[i] = tmp[i];
        }
    }
}

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> tmp(n);
        for (int i = 0; i < n; i++) {
            tmp[(i + k) % n] = nums[i];
        }
        for (int i = 0; i < n; i++) {
            nums[i] = tmp[i];
        }
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {void} Do not return anything, modify nums in-place instead.
     */
    rotate(nums, k) {
        const n = nums.length;
        const tmp = new Array(n);
        for (let i = 0; i < n; i++) {
            tmp[(i + k) % n] = nums[i];
        }
        for (let i = 0; i < n; i++) {
            nums[i] = tmp[i];
        }
    }
}

public class Solution {
    public void Rotate(int[] nums, int k) {
        int n = nums.Length;
        int[] tmp = new int[n];

        for (int i = 0; i < n; i++) {
            tmp[(i + k) % n] = nums[i];
        }

        for (int i = 0; i < n; i++) {
            nums[i] = tmp[i];
        }
    }
}

class Solution {
    fun rotate(nums: IntArray, k: Int) {
        val n = nums.size
        val tmp = IntArray(n)
        for (i in 0 until n) {
            tmp[(i + k) % n] = nums[i]
        }
        for (i in 0 until n) {
            nums[i] = tmp[i]
        }
    }
}

class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        let n = nums.count
        var tmp = [Int](repeating: 0, count: n)
        for i in 0..<n {
            tmp[(i + k) % n] = nums[i]
        }
        for i in 0..<n {
            nums[i] = tmp[i]
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ extra space.

3. Cyclic Traversal

Intuition

We can rotate in-place by following cycles. Starting from any position, we move the element to its destination, then move the displaced element to its destination, and so on until we return to the starting position. If the cycle doesn't cover all elements (which happens when n and k share a common divisor), we start a new cycle from the next position. This ensures every element is moved exactly once.

Algorithm

Compute k = k % n and initialize a counter for how many elements have been placed.
Start from index 0. For each starting index:
- Save the element at the current position.
- Move to the next position (current + k) % n, swap the saved element with the element there, and repeat.
- Stop when we return to the starting index.
If not all elements are placed, increment the starting index and repeat.
Continue until all n elements have been moved.

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n
        count = start = 0

        while count < n:
            current = start
            prev = nums[start]
            while True:
                next_idx = (current + k) % n
                nums[next_idx], prev = prev, nums[next_idx]
                current = next_idx
                count += 1

                if start == current:
                    break
            start += 1

public class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        int count = 0;

        for (int start = 0; count < n; start++) {
            int current = start;
            int prev = nums[start];
            do {
                int nextIdx = (current + k) % n;
                int temp = nums[nextIdx];
                nums[nextIdx] = prev;
                prev = temp;
                current = nextIdx;
                count++;
            } while (start != current);
        }
    }
}

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        int count = 0;

        for (int start = 0; count < n; start++) {
            int current = start;
            int prev = nums[start];
            do {
                int nextIdx = (current + k) % n;
                int temp = nums[nextIdx];
                nums[nextIdx] = prev;
                prev = temp;
                current = nextIdx;
                count++;
            } while (start != current);
        }
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {void} Do not return anything, modify nums in-place instead.
     */
    rotate(nums, k) {
        const n = nums.length;
        k %= n;
        let count = 0;

        for (let start = 0; count < n; start++) {
            let current = start;
            let prev = nums[start];
            do {
                const nextIdx = (current + k) % n;
                const temp = nums[nextIdx];
                nums[nextIdx] = prev;
                prev = temp;
                current = nextIdx;
                count++;
            } while (start !== current);
        }
    }
}

public class Solution {
    public void Rotate(int[] nums, int k) {
        int n = nums.Length;
        k %= n;
        int count = 0;

        for (int start = 0; count < n; start++) {
            int current = start;
            int prev = nums[start];

            do {
                int nextIdx = (current + k) % n;
                int temp = nums[nextIdx];
                nums[nextIdx] = prev;
                prev = temp;
                current = nextIdx;
                count++;
            } while (start != current);
        }
    }
}

func rotate(nums []int, k int) {
    n := len(nums)
    k %= n
    count := 0

    for start := 0; count < n; start++ {
        current := start
        prev := nums[start]
        for {
            nextIdx := (current + k) % n
            temp := nums[nextIdx]
            nums[nextIdx] = prev
            prev = temp
            current = nextIdx
            count++
            if start == current {
                break
            }
        }
    }
}

class Solution {
    fun rotate(nums: IntArray, k: Int) {
        val n = nums.size
        val kMod = k % n
        var count = 0

        var start = 0
        while (count < n) {
            var current = start
            var prev = nums[start]
            do {
                val nextIdx = (current + kMod) % n
                val temp = nums[nextIdx]
                nums[nextIdx] = prev
                prev = temp
                current = nextIdx
                count++
            } while (start != current)
            start++
        }
    }
}

class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        let n = nums.count
        let kMod = k % n
        var count = 0

        var start = 0
        while count < n {
            var current = start
            var prev = nums[start]
            repeat {
                let nextIdx = (current + kMod) % n
                let temp = nums[nextIdx]
                nums[nextIdx] = prev
                prev = temp
                current = nextIdx
                count += 1
            } while start != current
            start += 1
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

4. Using Reverse

Intuition

A clever observation: rotating an array by k is equivalent to moving the last k elements to the front. We can achieve this with three reversals. First, reverse the entire array. Now the last k elements are at the front, but in reverse order. Reverse the first k elements to fix their order. Finally, reverse the remaining elements to restore their original order.

Algorithm

Compute k = k % n.
Reverse the entire array from index 0 to n - 1.
Reverse the first k elements (from index 0 to k - 1).
Reverse the remaining elements (from index k to n - 1).

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n

        def reverse(l: int, r: int) -> None:
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l, r = l + 1, r - 1

        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

public class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;

        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    private void reverse(int[] nums, int l, int r) {
        while (l < r) {
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            l++;
            r--;
        }
    }
}

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;

        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

private:
    void reverse(vector<int>& nums, int l, int r) {
        while (l < r) {
            swap(nums[l], nums[r]);
            l++;
            r--;
        }
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {void} Do not return anything, modify nums in-place instead.
     */
    rotate(nums, k) {
        const n = nums.length;
        k %= n;

        const reverse = (l, r) => {
            while (l < r) {
                [nums[l], nums[r]] = [nums[r], nums[l]];
                l++;
                r--;
            }
        };

        reverse(0, n - 1);
        reverse(0, k - 1);
        reverse(k, n - 1);
    }
}

public class Solution {
    public void Rotate(int[] nums, int k) {
        int n = nums.Length;
        k %= n;

        Reverse(nums, 0, n - 1);
        Reverse(nums, 0, k - 1);
        Reverse(nums, k, n - 1);
    }

    private void Reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

func rotate(nums []int, k int) {
    n := len(nums)
    k %= n

    reverse := func(l, r int) {
        for l < r {
            nums[l], nums[r] = nums[r], nums[l]
            l++
            r--
        }
    }

    reverse(0, n-1)
    reverse(0, k-1)
    reverse(k, n-1)
}

class Solution {
    fun rotate(nums: IntArray, k: Int) {
        val n = nums.size
        val kMod = k % n

        fun reverse(l: Int, r: Int) {
            var left = l
            var right = r
            while (left < right) {
                val temp = nums[left]
                nums[left] = nums[right]
                nums[right] = temp
                left++
                right--
            }
        }

        reverse(0, n - 1)
        reverse(0, kMod - 1)
        reverse(kMod, n - 1)
    }
}

class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        let n = nums.count
        let kMod = k % n

        func reverse(_ l: Int, _ r: Int) {
            var left = l, right = r
            while left < right {
                let temp = nums[left]
                nums[left] = nums[right]
                nums[right] = temp
                left += 1
                right -= 1
            }
        }

        reverse(0, n - 1)
        reverse(0, kMod - 1)
        reverse(kMod, n - 1)
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

5. One Liner

Intuition

Many languages provide built-in ways to slice and concatenate arrays. We can simply take the last k elements and prepend them to the rest of the array. This leverages language features to express the rotation concisely, though under the hood it may use extra space.

Algorithm

Compute the effective rotation k % n.
Slice the array into two parts: the last k elements and the first n - k elements.
Concatenate them in reverse order and assign back to the original array.

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums[:] = nums[-k % len(nums):] + nums[:-k % len(nums)]

public class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] rotated = Arrays.copyOfRange(nums, n - k % n, n);
        System.arraycopy(nums, 0, nums, k % n, n - k % n);
        System.arraycopy(rotated, 0, nums, 0, rotated.length);
    }
}

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {void} Do not return anything, modify nums in-place instead.
     */
    rotate(nums, k) {
        nums.splice(0, 0, ...nums.splice(nums.length - (k % nums.length)));
    }
}

public class Solution {
    public void Rotate(int[] nums, int k) {
        int n = nums.Length;
        k %= n;

        int[] rotated = new int[n];
        Array.Copy(nums, n - k, rotated, 0, k);
        Array.Copy(nums, 0, rotated, k, n - k);
        Array.Copy(rotated, nums, n);
    }
}

class Solution {
    fun rotate(nums: IntArray, k: Int) {
        val n = nums.size
        val kMod = k % n
        val rotated = nums.takeLast(kMod) + nums.dropLast(kMod)
        for (i in nums.indices) {
            nums[i] = rotated[i]
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ or $O(n)$ depending on the language.

Common Pitfalls

Forgetting to Handle k Greater Than Array Length

When k is larger than the array length n, rotating by k is the same as rotating by k % n. Failing to normalize k with the modulo operation leads to unnecessary iterations or index out of bounds errors. Always compute k = k % n before proceeding.

Incorrect Reversal Boundaries in the Three-Reverse Approach

In the reverse approach, the three reversals must use precise boundaries: reverse the entire array, then reverse [0, k-1], then reverse [k, n-1]. Using wrong indices like reversing [0, k] instead of [0, k-1] shifts the boundary incorrectly and produces a wrong result.

Modifying Array While Iterating Without Proper Tracking

In the cyclic replacement approach, failing to track how many elements have been placed can cause infinite loops or incomplete rotations. This happens when n and k share a common divisor, creating multiple cycles. Always maintain a counter and start new cycles until all elements are moved.