Right Rotate an array by k elements

By /

An array of elements is given arr
arr is of length n
Right rotate array by k elements
Time complexity O(n) and space complexity O(1)

Sample Input:
arr = {1,2 ,3,4,5}
n = 5
k = 2
Output :
arr = {4,5,1,2,3}

2026 Update: Array Rotation — Three Techniques, One O(1) Space Winner

Rotating an array by k positions is a classic problem with multiple approaches. The interviewer wants to see you arrive at the O(n) time, O(1) space solution using reversal.

from collections import deque

def rotate_brute(nums: list, k: int) -> list:
    """O(n*k) time, O(1) space — rotate one element at a time."""
    n = len(nums)
    k %= n
    for _ in range(k):
        temp = nums[-1]
        for i in range(n - 1, 0, -1):
            nums[i] = nums[i - 1]
        nums[0] = temp
    return nums

def rotate_extra_space(nums: list, k: int) -> list:
    """O(n) time, O(n) space — copy to extra array."""
    n = len(nums)
    k %= n
    return nums[-k:] + nums[:-k]

def rotate_reversal(nums: list, k: int) -> None:
    """
    O(n) time, O(1) space — THREE-STEP REVERSAL.
    Right rotate by k: [1,2,3,4,5,6,7], k=3 → [5,6,7,1,2,3,4]
    """
    n = len(nums)
    k %= n

    def reverse(arr, left, right):
        while left  None:
    """O(n) time, O(1) space — cyclic replacements."""
    n = len(nums)
    k %= n
    count = 0  # Track how many elements have been placed
    start = 0
    while count  list:
    k %= len(nums)
    return nums[k:] + nums[:k]

print(left_rotate([1,2,3,4,5], 2))  # [3,4,5,1,2]

Key insight: The reversal trick works because rotating right by k = rotating left by (n-k). The three-reversal approach is the standard O(1) space answer. LeetCode #189. Common follow-up: “Rotate a matrix 90 degrees” — also uses transpose + reverse rows, same reversal insight in 2D.

💡Strategies for Solving This Problem

The Rotation Trick

Got this at Microsoft. It seems simple but most people do it the hard way with extra space. The elegant solution uses reversals - it's one of those "once you see it, you can't unsee it" tricks.

Naive Approach

Create a new array, copy elements to rotated positions. Works but uses O(n) extra space. Interviewer will ask "Can you do it in-place?"

The Reversal Trick

To rotate right by k positions:

  1. Reverse entire array
  2. Reverse first k elements
  3. Reverse remaining n-k elements

Example: [1,2,3,4,5] rotate right by 2

  • Reverse all: [5,4,3,2,1]
  • Reverse first 2: [4,5,3,2,1]
  • Reverse last 3: [4,5,1,2,3] ✓

O(n) time, O(1) space. This is what they want.

Why It Works

Think about it: rotation moves the last k elements to the front. By reversing, we're essentially moving them but in reverse order. Then we fix each part's order.

My Microsoft interviewer said "This is a classic trick. If you didn't know it before, you do now."

Edge Cases

  • k > n: Use k % n (rotating n times = original array)
  • k = 0 or k = n: No rotation needed
  • Empty array: Return as-is
Scroll to Top