Rotate an Array by K Places, thesarfo

Left-rotating [1,2,3,4,5] by one place gives [2,3,4,5,1] — the first element moves to the end. Rotating by k places moves the first k elements to the end. Since rotating by the array’s own length returns the original array, only k % n actually matters.

Brute force: store the first k elements in a temp array, shift everything else left by k, then place the temp array at the end.

vector<int> rotateArray(vector<int> arr, int k) {
    k = k % arr.size();

    int temp[k];
    for(int i = 0; i < k; i++){
        temp[i] = arr[i];
    }

    for(int i = k; i < arr.size(); i++){
        arr[i - k] = arr[i];
    }

    for(int i = arr.size() - k; i < arr.size(); i++){
        arr[i] = temp[i - (arr.size() - k)];
    }
    return arr;
}

Optimal — three reversals, no extra space: reverse the first k elements, reverse the rest, then reverse the whole array. For [1,2,3,4,5], k=3: reverse [1,2,3] → [3,2,1,4,5]; reverse [4,5] → [3,2,1,5,4]; reverse everything → [4,5,1,2,3].

public class Solution {
    public static void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }

    public static int[] rotateArray(int[] arr, int k) {
        int n = arr.length;
        k = k % n;

        reverse(arr, 0, k - 1);
        reverse(arr, k, n - 1);
        reverse(arr, 0, n - 1);

        return arr;
    }
}

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