Arrays, Strings & Cache Memory

This is a classic problem where the textbook solution and the production solution diverge. When you are moving 10 million integers in memory, allocating a temp slice or doing naive cyclic swaps will kill your performance due to cache misses.

The cleanest, most battle-tested way to do this in production is the 3-Reversal Trick (often called the Reversal Algorithm). It requires zero extra memory and traverses contiguous memory sequentially, which modern CPU prefetchers love.

1. The Intuition (Why 3 Reversals Work)

Suppose you have the array [1, 2, 3, 4, 5, 6, 7] and you want to rotate right by k = 3 (so [5, 6, 7, 1, 2, 3, 4]).

Notice the split: the last k elements need to move to the front, and the first n - k elements move to the back. If you reverse the whole thing first, everything is in the right neighborhood but backwards:

1. Reverse the entire array: [7, 6, 5, 4, 3, 2, 1]
2. Reverse the first k elements (0 to k-1): [5, 6, 7, 4, 3, 2, 1]
3. Reverse the remaining n-k elements (k to n-1): [5, 6, 7, 1, 2, 3, 4]

Done! Every element is now in its exact final position.

2. Production C++20 Implementation

#include <vector>
#include <algorithm>
#include <cstdint>

// In-place rotation using standard cache-friendly iterator reversal
void rotateArrayInPlace(std::vector<int32_t>& nums, size_t k) {
    const size_t n = nums.size();
    if (n <= 1) return;
    
    // Normalize k in case k > n
    k = k % n;
    if (k == 0) return;

    // Helper lambda for two-pointer swap
    auto reverseRange = [&nums](size_t start, size_t end) {
        while (start < end) {
            std::swap(nums[start], nums[end]);
            ++start;
            --end;
        }
    };

    // 1. Flip everything
    reverseRange(0, n - 1);
    // 2. Flip the first k
    reverseRange(0, k - 1);
    // 3. Flip the rest
    reverseRange(k, n - 1);
}

3. Python 3.12 Clean Version

def rotate_in_place(nums: list[int], k: int) -> None:
    """Rotates nums to the right by k steps in-place with O(1) extra space."""
    n = len(nums)
    if n <= 1:
        return
    k = k % n
    if k == 0:
        return

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

    # Step 1: reverse full list
    reverse(0, n - 1)
    # Step 2: reverse first k elements
    reverse(0, k - 1)
    # Step 3: reverse remaining elements
    reverse(k, n - 1)

4. Complexity Breakdown

• Time Complexity: O(N) total time. Step 1 does n/2 swaps, Step 2 does k/2 swaps, and Step 3 does (n-k)/2 swaps. Total swaps = exactly n swaps. You can't beat linear time because every element must change position.
• Space Complexity: O(1) auxiliary space. Just two index pointers living directly in CPU registers.
• Cache Friendliness: Because the pointers move inward in contiguous linear blocks, L1/L2 cache prefetching works at full hardware memory bandwidth.

5. Real-World Gotchas to Watch Out For

• When k > n: Always take k = k % n. Forgetting this causes out-of-bounds pointer crashes when k = 15 on an array of length 5.
• Negative k (Left Rotation): If your system asks for a left rotation by k, simply transform it: a left rotation by k is equivalent to a right rotation by (n - (k % n)) % n.
• Empty or Single Element Arrays: Check n <= 1 upfront to prevent unsigned integer underflow on n - 1.