Rotate Array

medium array two pointers

Problem

Given an array, rotate the array to the right by k steps, where k is non-negative.

Trick: reverse the entire array, then reverse the first k elements, then reverse the remaining n − k. The composition of three reversals lands every element at its rotated index.

Inputnums = [10, 20, 30, 40, 50, 60, 70], k = 3

Output[50, 60, 70, 10, 20, 30, 40]

nums (comma-separated)

def rotate(nums, k):
    n = len(nums)
    k %= n
    reverse(nums, 0, n - 1)
    reverse(nums, 0, k - 1)
    reverse(nums, k, n - 1)

def reverse(a, l, r):
    while l < r:
        a[l], a[r] = a[r], a[l]
        l += 1
        r -= 1

function rotate(nums, k) {
  const n = nums.length;
  k = k % n;
  reverse(nums, 0, n - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, n - 1);
}
function reverse(a, l, r) {
  while (l < r) { [a[l], a[r]] = [a[r], a[l]]; l++; r--; }
}

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
    void reverse(int[] a, int l, int r) {
        while (l < r) { int t = a[l]; a[l++] = a[r]; a[r--] = t; }
    }
}

void reverseRange(vector<int>& a, int l, int r) {
    while (l < r) swap(a[l++], a[r--]);
}
void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    k %= n;
    reverseRange(nums, 0, n - 1);
    reverseRange(nums, 0, k - 1);
    reverseRange(nums, k, n - 1);
}

Explanation

Rotating an array right by k means the last k elements jump to the front and everyone else slides back. The elegant in-place trick is three reversals, which lands every element exactly where it belongs without any extra array.

First we do k %= n because rotating by the full length brings you back to the start; only the remainder matters. Then we reverse the whole array, then reverse just the first k elements, then reverse the remaining n - k elements.

Why this works: reversing the whole array brings the would-be front block to the front but in backwards order; reversing each of the two sections separately flips them back into their correct internal order. The composition of the three flips equals a clean right rotation.

Example: nums = [10,20,30,40,50,60,70], k = 3. Reverse all → [70,60,50,40,30,20,10]. Reverse first 3 → [50,60,70,40,30,20,10]. Reverse last 4 → [50,60,70,10,20,30,40]. That is the rotation.

Each reversal is a simple two-pointer swap, so the whole thing is linear time and uses only constant extra memory.

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