LeetCode 189: Rotate Array

Problem Restatement

We are given an integer array nums and an integer k.

We need to rotate the array to the right by k steps.

Rotating right by one step means the last element moves to the front, and every other element shifts one position to the right.

We must modify nums in-place.

Input and Output

Example function shape:

def rotate(nums: list[int], k: int) -> None:
    ...

Examples

Example 1:

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

Rotate right once:

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

Rotate right twice:

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

Rotate right three times:

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

So the final array is:

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

Example 2:

nums = [-1, -100, 3, 99]
k = 2

After rotating right by 2 steps:

[3, 99, -1, -100]

First Thought: Move One Step at a Time

A simple idea is to rotate the array one step, then repeat this k times.

For one right rotation:

1. Save the last element.
2. Shift every other element one position right.
3. Put the saved last element at index 0.

This works, but it costs O(n) time for each step.

If we repeat it k times, the time complexity is:

O(nk)

This is too slow when k is large.

Key Insight

A rotation by k steps splits the array into two parts.

For:

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

The last k elements should move to the front:

[5, 6, 7]

The earlier elements should move after them:

[1, 2, 3, 4]

So the result is:

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

We can create this in-place using three reversals.

Start:

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

Reverse the whole array:

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

Reverse the first k elements:

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

Reverse the remaining elements:

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

Now the array is rotated correctly.

Algorithm

1. Let n = len(nums).
2. Reduce k using modulo:

k %= n

3. Reverse the whole array.
4. Reverse the first k elements.
5. Reverse the remaining n - k elements.

The modulo step matters because rotating by n steps gives the same array.

For example:

k = 10
n = 7

Rotating by 10 steps is the same as rotating by:

10 % 7 = 3

steps.

Correctness

Let the original array be split into two parts:

A B

where B is the last k elements and A is everything before it.

The target rotated array is:

B A

When we reverse the whole array, we get:

reverse(B) reverse(A)

Then we reverse the first k elements. This changes reverse(B) back into B.

Now the array is:

B reverse(A)

Then we reverse the remaining elements. This changes reverse(A) back into A.

The final array is:

B A

That is exactly the array rotated right by k steps.

Complexity

Implementation

class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        n = len(nums)
        k %= n

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

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

Code Explanation

This gets the array length:

n = len(nums)

This reduces unnecessary full rotations:

k %= n

If k is larger than n, only the remainder matters.

The helper function reverses a section of the array:

def reverse(left: int, right: int) -> None:

It swaps the two ends and moves inward:

nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1

Then we apply the three-reversal method:

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

The first reversal puts the last k elements near the front, but reversed.

The second reversal fixes those k elements.

The third reversal fixes the remaining elements.

Alternative Implementation With Extra Array

This version is simpler, but uses O(n) extra space.

class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        n = len(nums)
        k %= n

        rotated = nums[-k:] + nums[:-k]

        for i in range(n):
            nums[i] = rotated[i]

For interviews, the in-place reversal version is usually preferred.

Testing

def run_tests():
    s = Solution()

    nums = [1, 2, 3, 4, 5, 6, 7]
    s.rotate(nums, 3)
    assert nums == [5, 6, 7, 1, 2, 3, 4]

    nums = [-1, -100, 3, 99]
    s.rotate(nums, 2)
    assert nums == [3, 99, -1, -100]

    nums = [1]
    s.rotate(nums, 0)
    assert nums == [1]

    nums = [1, 2]
    s.rotate(nums, 3)
    assert nums == [2, 1]

    nums = [1, 2, 3]
    s.rotate(nums, 3)
    assert nums == [1, 2, 3]

    print("all tests passed")

run_tests()

Test meaning: