Rotate Array

Difficulty: Medium Source: NeetCode

Problem

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. Do this in-place with O(1) extra space.

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

Example 2: Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100]

Constraints:

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

Prerequisites

Before attempting this problem, you should be comfortable with:

• Arrays — in-place modification and slicing
• Two Pointers — the reverse trick for rotating sequences
• Modular Arithmetic — handling k >= len(nums) with k % n

1. Brute Force

Intuition

Allocate a new array of the same size. Each element at index i ends up at index (i + k) % n after rotation. Fill the new array using this mapping, then copy it back into nums. Simple and correct, but uses O(n) extra space.

Algorithm

1. Compute n = len(nums) and k = k % n.
2. Create rotated = [0] * n.
3. For each i, set rotated[(i + k) % n] = nums[i].
4. Copy rotated back into nums.

Solution

def rotate(nums, k):
    n = len(nums)
    k = k % n
    rotated = [0] * n
    for i in range(n):
        rotated[(i + k) % n] = nums[i]
    for i in range(n):
        nums[i] = rotated[i]


nums = [1, 2, 3, 4, 5, 6, 7]
rotate(nums, 3)
print(nums)  # [5, 6, 7, 1, 2, 3, 4]

nums = [-1, -100, 3, 99]
rotate(nums, 2)
print(nums)  # [3, 99, -1, -100]

Complexity

• Time: O(n)
• Space: O(n)

2. Three Reverses

Intuition

Here’s the clever trick: rotating right by k is equivalent to:

1. Reversing the entire array.
2. Reversing the first k elements.
3. Reversing the last n - k elements.

Try it on [1,2,3,4,5,6,7] with k=3:

• Reverse all → [7,6,5,4,3,2,1]
• Reverse first 3 → [5,6,7,4,3,2,1]
• Reverse last 4 → [5,6,7,1,2,3,4] ✓

Each reversal is done with two pointers (swap from both ends), so the whole operation is O(n) time and O(1) space.

Algorithm

1. Compute k = k % n to handle k >= n.
2. Define reverse(nums, left, right) — swap elements inward until left >= right.
3. Call reverse(nums, 0, n - 1) — reverse entire array.
4. Call reverse(nums, 0, k - 1) — reverse first k elements.
5. Call reverse(nums, k, n - 1) — reverse last n - k elements.

Solution

def rotate(nums, k):
    n = len(nums)
    k = k % n

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

    reverse(0, n - 1)   # Reverse the whole array
    reverse(0, k - 1)   # Reverse the first k elements
    reverse(k, n - 1)   # Reverse the remaining n-k elements


nums = [1, 2, 3, 4, 5, 6, 7]
rotate(nums, 3)
print(nums)  # [5, 6, 7, 1, 2, 3, 4]

nums = [-1, -100, 3, 99]
rotate(nums, 2)
print(nums)  # [3, 99, -1, -100]

nums = [1, 2]
rotate(nums, 3)
print(nums)  # [2, 1]

Complexity

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

Common Pitfalls

Not reducing k with modulo. If k >= n, the rotation wraps around. k = k % n handles this — and if k becomes 0, no rotation is needed (all three reverses would be no-ops anyway).

Off-by-one in the second and third reversal bounds. The first k elements span indices 0 to k - 1 (inclusive). The remaining elements span k to n - 1. Getting one of these bounds wrong produces a partially-rotated array that looks almost correct.

Using nums[:] = nums[-k:] + nums[:-k] and thinking it’s O(1). Python slice assignment creates new list objects, so this is O(n) space despite looking clean. It’s a valid one-liner for interviews where space complexity isn’t tested, but don’t claim it’s in-place.