Rotate an Array by k Places

medium array two pointers

Problem

Cyclically shift the array to the right by k positions, modifying it in place. Use only O(1) extra space.

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);
}

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