K Rotations (Right)

The Problem

Given an array arr and a non-negative number k, rotate the array by k steps to the right — in-place, using O(1) extra space.

Example 1:

Input:  arr = [1, 2, 3, 4, 5], k = 3
Output: [3, 4, 5, 1, 2]

Rotate 1 step right  →  [5, 1, 2, 3, 4]
Rotate 2 steps right →  [4, 5, 1, 2, 3]
Rotate 3 steps right →  [3, 4, 5, 1, 2]

Example 2:

Input:  arr = [1, 2, 3, 4, 5], k = 5
Output: [1, 2, 3, 4, 5]    ← rotating n times returns the original

Example 3:

Input:  arr = [1, 2, 3, 4, 5], k = 0
Output: [1, 2, 3, 4, 5]

What Does “Rotate Right” Mean?

One step to the right means the last element wraps around to the front, and every other element shifts one position to the right.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
    A["[1, 2, 3, 4, 5]"] -->|"rotate right 1"| B["[5, 1, 2, 3, 4]"]
    B -->|"rotate right 2"| C["[4, 5, 1, 2, 3]"]
    C -->|"rotate right 3"| D["[3, 4, 5, 1, 2]"]

Each right rotation brings the last element to the front — after k=3 steps, the last 3 elements form the new prefix.

After k right rotations, the last k elements end up at the front, and the first n-k elements shift to the back.

Think of it as splitting the array into two halves: [HEAD | TAIL] where HEAD = first n-k elements and TAIL = last k elements. The goal is to produce [TAIL | HEAD].

Applying the Diagnostic Questions

Q1 — Why “right rotation = 3 in-place reversals”?

This is the same fundamental insight from the previous lesson, adapted for the direction of rotation.

Mental model: Split the array into [HEAD | TAIL]. A right rotation by k wants to produce [TAIL | HEAD]. Reversing each half individually scrambles their internal order, but a final full reversal restores both halves while swapping their positions.

The three steps:

1. Reverse TAIL (last k elements): internal order flips → [HEAD | TAIL_reversed]
2. Reverse HEAD (first n-k elements): internal order flips → [HEAD_reversed | TAIL_reversed]
3. Reverse the entire array: everything flips, which un-reverses both halves and places TAIL before HEAD → [TAIL | HEAD] ✓

Concrete check with [1, 2, 3, 4, 5], k=3:

• HEAD = [1, 2] (first 2), TAIL = [3, 4, 5] (last 3)
• Step 1 (reverse TAIL [2..4]): [1, 2, 5, 4, 3]
• Step 2 (reverse HEAD [0..1]): [2, 1, 5, 4, 3]
• Step 3 (reverse all [0..4]): [3, 4, 5, 1, 2] ✓

What breaks if you skip the segment reversals? If you only reversed the entire array: [1,2,3,4,5] → [5,4,3,2,1]. That’s a full reversal, not a rotation. The two preparatory reversals are what guarantee each half’s internal order is preserved after the final flip.

How this differs from left rotation: The previous lesson solved left rotation by reversing the first k elements, then the last n-k, then the whole array. For right rotation, the segment sizes are swapped — you reverse the last k and the first n-k first, then the whole array. The same mechanic, with HEAD and TAIL switched.

Q2 — Why “in-place reversal is the two-pointer flip”?

Reversing a segment [start..end] is the canonical two-pointer direct application:

• Place left at start, right at end
• Swap arr[left] and arr[right], move left inward, right inward
• Stop when left >= right

Why two pointers? The reversal problem has perfect bilateral symmetry — element at position i from the left swaps with position i from the right. Two pointers exploit this directly, doing both jobs simultaneously from the outside in.

What if you didn’t use two pointers? You’d need a temporary array to hold the reversed segment before writing it back — O(k) extra space per reversal. Two pointers do it with only two index variables — O(1) per reversal, O(1) total.

The Three-Reversal Strategy (Visualised)

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
    subgraph S0["Original:  [1, 2 | 3, 4, 5]  (HEAD=2, TAIL=3)"]
        direction LR
        A1["1"] --- A2["2"] --- A3["3"] --- A4["4"] --- A5["5"]
    end
    subgraph S1["Step 1: Reverse TAIL  [2..4]  →  [1, 2, 5, 4, 3]"]
        direction LR
        B1["1"] --- B2["2"] --- B3["5"] --- B4["4"] --- B5["3"]
    end
    subgraph S2["Step 2: Reverse HEAD  [0..1]  →  [2, 1, 5, 4, 3]"]
        direction LR
        C1["2"] --- C2["1"] --- C3["5"] --- C4["4"] --- C5["3"]
    end
    subgraph S3["Step 3: Reverse all  [0..4]  →  [3, 4, 5, 1, 2]  ✓"]
        direction LR
        D1["3"] --- D2["4"] --- D3["5"] --- D4["1"] --- D5["2"]
    end
    S0 -->|"reverse arr[2..4]"| S1
    S1 -->|"reverse arr[0..1]"| S2
    S2 -->|"reverse arr[0..4]"| S3

Right rotation by k=3 via three in-place reversals — each reversal is an independent two-pointer subproblem.

The Solution

from typing import List

class Solution:
    def reverse(self, arr: List[int], start: int, end: int) -> None:
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]  # Swap the outermost unseen pair
            start += 1  # Shrink window from the left
            end   -= 1  # Shrink window from the right
        # When start >= end, every pair has been swapped — segment is fully reversed

    def rotate_right(self, arr: List[int], k: int) -> None:
        n = len(arr)
        k %= n  # Rotating n times is a no-op; reduce k to its effective range [0, n-1]

        if k == 0:
            return  # Nothing to do — handles k=0 and k=n cleanly

        # Split: HEAD = arr[0..n-k-1], TAIL = arr[n-k..n-1]
        # Goal:  [TAIL | HEAD]
        self.reverse(arr, n - k, n - 1)   # Step 1: Reverse TAIL  →  scramble it for the final flip
        self.reverse(arr, 0, n - k - 1)   # Step 2: Reverse HEAD  →  scramble it for the final flip
        self.reverse(arr, 0, n - 1)        # Step 3: Reverse all   →  un-scrambles both halves in swapped positions


arr = [1, 2, 3, 4, 5]
Solution().rotate_right(arr, 3)
print(arr)  # Expected: [3, 4, 5, 1, 2]

n = 5,  k = 3 % 5 = 3
HEAD = arr[0..1] = [1, 2],  TAIL = arr[2..4] = [3, 4, 5]

━━━ Step 1: reverse(arr, 2, 4) — flip TAIL [2..4] ━━━
  start=2 (3), end=4 (5)  │  2 < 4 → swap 3↔5  →  [1, 2, 5, 4, 3]  │  start=3, end=3
  start=3 (4), end=3 (4)  │  3 == 3 → stop (middle element, no swap)
After step 1: [1, 2, 5, 4, 3]

━━━ Step 2: reverse(arr, 0, 1) — flip HEAD [0..1] ━━━
  start=0 (1), end=1 (2)  │  0 < 1 → swap 1↔2  →  [2, 1, 5, 4, 3]  │  start=1, end=0
  start=1, end=0           │  1 > 0 → stop
After step 2: [2, 1, 5, 4, 3]

━━━ Step 3: reverse(arr, 0, 4) — flip entire array [0..4] ━━━
  start=0 (2), end=4 (3)  │  0 < 4 → swap 2↔3  →  [3, 1, 5, 4, 2]  │  start=1, end=3
  start=1 (1), end=3 (4)  │  1 < 3 → swap 1↔4  →  [3, 4, 5, 1, 2]  │  start=2, end=2
  start=2 (5), end=2 (5)  │  2 == 2 → stop (middle element, no swap)
After step 3: [3, 4, 5, 1, 2] ✓

Result: [3, 4, 5, 1, 2]
The last 3 elements are now the prefix; original relative order within each group is preserved.

Complexity Analysis

Edge Cases

Left vs. Right Rotation — The Relationship

Right rotation by k is identical to left rotation by n - k. Both use the same three-reversal trick; only the segment sizes in steps 1 and 2 are swapped:

The core mechanic is identical — what changes is which segment you call HEAD and which you call TAIL.

Final Takeaway

A right rotation by k splits the array into [HEAD | TAIL] and produces [TAIL | HEAD]. The three-reversal trick achieves this in O(n) time, O(1) space: scramble TAIL, scramble HEAD, flip everything — the final reversal restores both halves’ internal order while landing them in swapped positions. Always normalize k with k %= n first to eliminate redundant rotations.