189. Rotate Array

Reformulated question¶

Rotate nums in-place to the right by k positions.

Compact example:

nums=[1,2,3,4,5,6,7], k=3 -> nums becomes [5,6,7,1,2,3,4]

Key trick¶

Reduce useless work first:

k %= len(nums)

Then the clean in-place solution is:

reverse all
reverse first k
reverse the rest

Trap¶

Common mistakes:

forgetting k %= n
crashing when k > n
returning a new list instead of modifying nums in-place
off-by-one errors in reverse boundaries
special-casing too much instead of handling k == 0 naturally

Why is this question interesting?¶

It tests simple index mapping, in-place mutation, and whether you know the reverse trick that turns a seeming shift problem into a few local swaps.

Solve the problem with idiomatic python¶

class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        # In-place O(1) extra space solution using 3 reverses.
        #
        # Think of nums as [A | B]:
        # A = nums[:n-k], B = nums[n-k:]
        #
        # We want [B | A].
        #
        # 1) reverse all:
        #    [A | B] -> [reverse(B) | reverse(A)]
        #
        # 2) reverse first k:
        #    [reverse(B) | reverse(A)] -> [B | reverse(A)]
        #
        # 3) reverse last n-k:
        #    [B | reverse(A)] -> [B | A]
        n = len(nums)
        k %= n
        if k == 0:
            return

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

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

Exact-problem library-style shortcut:

class SolutionSlice:
    def rotate(self, nums: list[int], k: int) -> None:
        # Very pythonic, but uses O(n) extra space.
        n = len(nums)
        k %= n
        nums[:] = nums[-k:] + nums[:-k]

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("nums", "k", "expected"),
    [
        ([1, 2, 3, 4, 5, 6, 7], 3, [5, 6, 7, 1, 2, 3, 4]),
        ([-1, -100, 3, 99], 2, [3, 99, -1, -100]),
        ([1], 0, [1]),
        ([1], 10, [1]),
        ([1, 2], 1, [2, 1]),
        ([1, 2], 2, [1, 2]),
        ([1, 2], 3, [2, 1]),
        ([1, 2, 3, 4], 4, [1, 2, 3, 4]),
        ([1, 2, 3, 4], 6, [3, 4, 1, 2]),
        ([1, 2, 3, 4, 5], 0, [1, 2, 3, 4, 5]),
    ],
)
def test_rotate_array(nums, k, expected):
    Solution().rotate(nums, k)
    assert nums == expected

Comment my solution¶

Solution:

It is not O(1) extra space because queue uses up to k elements.
It breaks for k > n because num_step = n // k + 1 becomes too small and the rotation is incomplete.
It also does unnecessary complicated state handling with None sentinels.
The reverse solution is shorter, correct, and truly in-place.

Solution2:

This one is correct and simple.
Add k %= n first for clarity and efficiency.
nums[:] = new is enough; new[:] is unnecessary.

import pytest

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

        n = len(nums)

        # the (at most k) elements in queue are the elements
        # being rotated at each step
        queue = []

        for i in range(k):
            if i < n:
                queue.append(nums[i])
            else:
                queue.append(None)

        num_step = n // k + 1

        for step in range(1, num_step + 1):
            idx = step * k
            for i in range(k):
                # swap queue and nums
                if queue[i] is not None:
                    to_queue = None if ((idx + i) >= n) else nums[(idx + i) % n]
                    nums[(idx + i) % n] = queue[i]
                    queue[i] = to_queue

class Solution2:
    def rotate(self, nums: list[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # O(n) extra space
        # new[(i + k) % n] = nums[i]
        # new[i] = nums[(i - k) % n]
        n = len(nums)
        new = [0] * n
        for i in range(n):
            new[i] = nums[(i - k) % n]
        nums[:] = new[:]

@pytest.mark.parametrize(
    ("nums", "k", "expected"),
    [([1,2,3,4,5,6,7], 3, [5,6,7,1,2,3,4]),
     ([1,2,3,4,5,6,7,8,9], 2, [8,9,1,2,3,4,5,6,7]),
     ([1,2,3,4], 4, [1,2,3,4]),
     ([1,2], 3, [2, 1]),
]
)
def test_rotate_array(nums, k, expected):
    Solution().rotate(nums, k)
    assert nums == expected

Code¶

import pytest


class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        # In-place O(1) extra space solution using 3 reverses.
        n = len(nums)
        k %= n
        if k == 0:
            return

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

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


class SolutionSlice:
    def rotate(self, nums: list[int], k: int) -> None:
        # Simpler but uses O(n) extra space.
        n = len(nums)
        k %= n
        nums[:] = nums[-k:] + nums[:-k]


@pytest.mark.parametrize(
    ("nums", "k", "expected"),
    [
        ([1, 2, 3, 4, 5, 6, 7], 3, [5, 6, 7, 1, 2, 3, 4]),
        ([-1, -100, 3, 99], 2, [3, 99, -1, -100]),
        ([1], 0, [1]),
        ([1], 10, [1]),
        ([1, 2], 1, [2, 1]),
        ([1, 2], 2, [1, 2]),
        ([1, 2], 3, [2, 1]),
        ([1, 2, 3, 4], 4, [1, 2, 3, 4]),
        ([1, 2, 3, 4], 6, [3, 4, 1, 2]),
        ([1, 2, 3, 4, 5], 0, [1, 2, 3, 4, 5]),
    ],
)
def test_rotate_array(nums, k, expected):
    Solution().rotate(nums, k)
    assert nums == expected


a = [1, 2, 3, 4, 5, 6, 7]
Solution().rotate(a, 3)
a

b = [-1, -100, 3, 99]
Solution().rotate(b, 2)
b

c = [1, 2, 3, 4]
SolutionSlice().rotate(c, 6)
c