Rotate Array

Q: What happens when k is larger than the array length?

Every n steps bring the array back to its starting order, so only k mod n steps matter. Rotating [10, 20, 30] by 7 is the same as rotating it by 1, which gives [30, 10, 20] . When k is a multiple of n , the array does not change.

Q: How do you rotate an array to the left?

A left rotation by k is a right rotation by n - (k mod n) . With reversals, reverse the first k mod n values, then the rest, then the whole array. Both stay O(n) time.

MediumArrays and strings Two pointers

+10

You get an array of integers nums and a number k. Rotate the array to the right by k steps: in one step every value moves one place to the right, and the last value wraps around to the front. Return the rotated array.

k can be far larger than the length of the array.

Function

rotate(nums: integer-array, k: integer) → integer-array

numsinteger-array: the array of integers to rotate
kinteger: how many steps to rotate to the right
Returnsinteger-array: nums rotated to the right by k steps

Constraints

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
0 ≤ k ≤ 10⁹

Examples

Input: nums = [4, 9, 1, 6, 3]k = 2
Output: [6, 3, 4, 9, 1]
Explanation: Two steps to the right carry the last two values, 6 and 3, around to the front. The other three values move two places right and keep their order: [6, 3, 4, 9, 1].

Follow-up

Can you rotate in place by moving each value straight to (i + k) mod n and carrying the value it displaces onward? How many cycles does that make?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Every n steps bring the array back to where it began, so first reduce k, which can be 10^9, to k mod n. Then write each value straight to its final index in a second array, or reach the same result inside the array with three reversals and O(1) extra memory.

Copy each value to its new index

Intuition

After k steps, the value at index i sits at (i + k) mod n, so write it there directly without doing the steps. Reduce k to k mod n first: a rotation by n puts every value back where it was, so with k = 7 and n = 3 one step is all that is left.

One pass places all n values: O(n) time, plus O(n) memory for the result. You cannot write into nums itself this way, because each write would overwrite a value you have not moved yet.

Algorithm

Set n to the length of nums and replace k with k mod n.
Create a result array of length n.
For every index i, store nums[i] at result[(i + k) mod n].
Return the result.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing
    result = [0] * n
    for i in range(n):
        result[(i + k) % n] = nums[i]
    return result

Three reversals in place

Intuition

Split the array into A, the first n-k values, and B, the last k. The rotated array is B followed by A, each block in its old order. Reversing the whole array flips both the order of the blocks and the order inside each one, so B comes first but reads backwards, and so does A. Reversing each block again restores its inner order.

For [4, 9, 1, 6, 3] and k = 2: reversing everything gives [3, 6, 1, 9, 4], reversing the first two gives [6, 3, 1, 9, 4], and reversing the last three gives [6, 3, 4, 9, 1].

Each value is swapped at most twice, so the time is O(n) and the extra memory is a few index variables (O(n) in R, which copies the vector when the reversal helper changes it).

Algorithm

Set n to the length of nums and replace k with k mod n.
Reverse the whole array, indices 0 to n-1.
Reverse the first block, indices 0 to k-1.
Reverse the second block, indices k to n-1.
Return nums.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing

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

    reverse(0, n - 1)  # the last k values come to the front, backwards
    reverse(0, k - 1)  # put the front block back in order
    reverse(k, n - 1)  # and the back block
    return nums

Pitfalls and edge cases

Forgetting k mod n. With k = 10^9, rotating step by step never finishes, and reversing the first k values reads far past the end of the array.
Slicing without the modulo. In Python, nums[-k:] + nums[:-k] with k = 7 and n = 3 returns the array unchanged, because both slices stop at the edge of the array.
Reversing in the wrong order. Reversing the two blocks first and the whole array last is a left rotation.
Off by one at the block edge: the first block ends at index k-1 and the second starts at k. In Lua and R, which count from 1, the blocks are 1..k and k+1..n.

Frequently asked questions3

What is the time complexity of Rotate Array?

O(n) for both the copy approach and the three reversals, because each value is moved a constant number of times. Reducing k with k mod n first keeps a huge k from mattering. Rotating one step at a time costs O(n × k) instead.

What happens when k is larger than the array length?

Every n steps bring the array back to its starting order, so only k mod n steps matter. Rotating [10, 20, 30] by 7 is the same as rotating it by 1, which gives [30, 10, 20]. When k is a multiple of n, the array does not change.

How do you rotate an array to the left?

A left rotation by k is a right rotation by n - (k mod n). With reversals, reverse the first k mod n values, then the rest, then the whole array. Both stay O(n) time.

def rotate(nums, k):
    # Write code here

Test #1

Test #2

Test #3

Arguments

nums = [4, 9, 1, 6, 3]
k = 2

Expected Output

[6, 3, 4, 9, 1]