Array after K Rotations

Given an array arr[] and an integer k, rotate the array in place k times to the right (clockwise). In each rotation, the last element moves to the front, and all other elements shift one position to the right. Modify the array in place, do not return anything.

Examples : 

Input: arr[] = [1, 2, 3, 4, 5, 6], k =2.
Output: [5, 6, 1, 2, 3, 4]
Explanation: After 1st rotation → [6, 1, 2, 3, 4, 5], After 2nd rotation → [5, 6, 1, 2, 3, 4]

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

[Naive Approach] Using Recursion - O(n*k) Time and O(k) Space

The main idea of this approach is to rotate the array to the right by one position, k times, using recursion. In each recursive call, the last element of the array is stored temporarily, all other elements are shifted one position to the right, and the saved element is placed at the front. This operation effectively performs a single right rotation. The function then calls itself with k - 1 until k reaches zero, at which point the recursion stops.

#include <iostream> #include <vector> using namespace std; void rotateclockwise(vector<int> &arr, int k) {  if (k == 0) {  return;  }  int n = arr.size();  if (n == 0) return;  // Rotate array to the right by 1 position  int temp = arr[n - 1];  for (int i = n - 1; i > 0; i--) {  arr[i] = arr[i - 1];  }  arr[0] = temp;  // Recursive call for remaining k-1 rotations  rotateclockwise(arr, k - 1); } int main() {  vector<int> arr = {1, 2, 3, 4, 5, 6};  int k = 2;  rotateclockwise(arr, k);  for (auto it : arr) {  cout << it << " ";  }  return 0; } 

import java.util.*; class GfG{  public static void rotateclockwise(int[] arr, int k) {  if (k == 0 || arr.length == 0) {  return;  }  int n = arr.length;  // Rotate right by one position  int temp = arr[n - 1];  for (int i = n - 1; i > 0; i--) {  arr[i] = arr[i - 1];  }  arr[0] = temp;  // Recursive call for k - 1  rotateclockwise(arr, k - 1);  }  public static void main(String[] args) {  int[] arr = {1, 2, 3, 4, 5, 6};  int k = 2;  rotateclockwise(arr, k);  for (int num : arr) {  System.out.print(num + " ");  }  } } 

def rotateclockwise(arr, k): if k == 0: return n = len(arr) # rotate the array to the right by one position temp = arr[n - 1] for i in range(n - 1, 0, -1): arr[i] = arr[i - 1] arr[0] = temp # recursively rotate the remaining elements k-1 times rotateclockwise(arr, k - 1) if __name__ == "__main__": arr = [1, 2, 3, 4, 5, 6] k = 2 rotateclockwise(arr, k) for it in arr: print(it, end=" ") 

using System; class GfG{  static void rotateclockwise(int[] arr, int k) {    if (k == 0 || arr.Length == 0) {  return;  }  int n = arr.Length;  // rotate the array to the right by one position  int temp = arr[n - 1];  for (int i = n - 1; i > 0; i--) {  arr[i] = arr[i - 1];  }  arr[0] = temp;  // recursively rotate the array k - 1 times  rotateclockwise(arr, k - 1);  }  static void Main() {  int[] arr = { 1, 2, 3, 4, 5, 6};  int k = 2;  rotateclockwise(arr, k);  foreach (int it in arr) {  Console.Write(it + " ");  }  } } 

function rotateclockwise(arr, k) {    if (k === 0 || arr.length === 0) {  return;  }  let n = arr.length;  // Rotate the array to the right by one position  let temp = arr[n - 1];  for (let i = n - 1; i > 0; i--) {  arr[i] = arr[i - 1];  }  arr[0] = temp;  // Recursive call for remaining k - 1 rotations  rotateclockwise(arr, k - 1); } // Driver Code let arr = [1, 2, 3, 4, 5, 6]; let k = 2; rotateclockwise(arr, k);  console.log(arr.join(" ")); 

5 6 1 2 3 4 

Time Complexity: O(n * k), because for each of the k rotations, the algorithm shifts all n elements by one position.
Auxiliary Space: O(k), due to the recursive call stack growing k levels deep, with no additional arrays used.

[Better Approach] Using Extra Space - O(n) Time and O(n) Space

The main idea is to first ensures that k is within bounds by taking k % n, where n is the array size. Then, we create a temporary result array where the last k elements of the original array are placed at the beginning. The remaining n - k elements are then copied after these. Finally, we copy all elements from the result array back to the original array to achieve an in-place update. This method uses index arithmetic to calculate positions efficiently.

#include <iostream> #include <vector> using namespace std;   void rotateclockwise(vector<int>& arr, int k) {  int n = arr.size();  // Handle cases where k > n  k = k % n;  // Temporary vector to store rotated elements  vector<int> res;  for (int i = 0; i < n; i++) {  if (i < k) {  // Add last k elements to front  res.push_back(arr[n + i - k]);  }   else {  // Shift remaining elements  res.push_back(arr[i - k]);  }  }  // Copy rotated result back to original array  for (int i = 0; i < n; i++) {  arr[i] = res[i];  } } int main() {    vector<int> arr = {1, 2, 3, 4, 5, 6};  int k = 2;    rotateclockwise(arr, k);  for (auto it : arr) {  cout << it << " ";  }  return 0; } 

import java.util.*; class GfG {  public static void rotateclockwise(int[] arr, int k) {  int n = arr.length;  // If rotation is greater than array size  k = k % n;  // Temporary array to store rotated elements  int[] res = new int[n];  for (int i = 0; i < n; i++) {  if (i < k) {  // Place last k elements at the beginning  res[i] = arr[n + i - k];  }   else {  // Shift the rest  res[i] = arr[i - k];  }  }  // Copy back to original array (in-place update)  for (int i = 0; i < n; i++) {  arr[i] = res[i];  }  }  public static void main(String[] args) {    int[] arr = {1, 2, 3, 4, 5, 6};  int k = 2;    rotateclockwise(arr, k);  for (int it : arr) {  System.out.print(it + " ");  }  } } 

def rotateclockwise(arr, k): n = len(arr) # If rotation count is greater than array size k = k % n # Temporary list to store rotated elements res = [0] * n for i in range(n): if i < k: # Place last k elements at front res[i] = arr[n + i - k] else: # Shift remaining elements res[i] = arr[i - k] # Copy result back to original array (in-place update) for i in range(n): arr[i] = res[i] # Driver code if __name__ == "__main__": arr = [1, 2, 3, 4, 5, 6] k = 2 rotateclockwise(arr, k) for it in arr: print(it, end=" ") 

using System; class GfG{    static void rotateclockwise(int[] arr, int k){    int n = arr.Length;  k = k % n;  // Create a temporary array to store result  int[] temp = new int[n];  for (int i = 0; i < n; i++){    // Calculate new position after rotation  int newIndex = (i + k) % n;  temp[newIndex] = arr[i];  }  // Copy back to original array (in-place update)  for (int i = 0; i < n; i++){    arr[i] = temp[i];  }  }  static void Main(){    int[] arr = { 1, 2, 3, 4, 5, 6 };  int k = 2;    rotateclockwise(arr, k);  foreach (int it in arr){    Console.Write(it + " ");  }  } } 

function rotateClockwise(arr, k) {  const n = arr.length;  // Handle cases where k > n  k = k % n;  // Temporary array to store rotated elements  let res = [];  for (let i = 0; i < n; i++) {  if (i < k) {    // Add last k elements to the front  res.push(arr[n + i - k]);  }   else {    // Shift remaining elements  res.push(arr[i - k]);  }  }  // Copy rotated result back to original array  for (let i = 0; i < n; i++) {  arr[i] = res[i];  } } // Driver Code let arr = [1, 2, 3, 4, 5, 6]; let k = 2; rotateclockwise(arr, k); console.log(arr.join(" ")); 

5 6 1 2 3 4 

[Expected Approach] Using Reversal Technique - O(n) Time and O(1)

Observing the Pattern:

Take the example arr[] = [1, 2, 3, 4, 5, 6] with k = 2.
After rotating the array to the right by 2 positions, we get:
[5, 6, 1, 2, 3, 4]

This shows that the last k elements (5, 6) move to the front in the same order, while the first n - k elements (1, 2, 3, 4) shift to the right.

How to Achieve This Efficiently:
Instead of shifting elements one by one, we can use the reversal algorithm, which works in three simple steps:

1. Reverse the last k elements.
2. Reverse the first n - k elements.
3. Reverse the entire array.

 Illustration:

#include<iostream> #include<vector> using namespace std; void rotateclockwise(vector<int>& arr, int k) {  int n = arr.size();  if (n == 0) return;  k = k % n;  int i, j;  // Reverse last k elements  for (i = n - k, j = n - 1; i < j; i++, j--) {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  // Reverse first n - k elements  for (i = 0, j = n - k - 1; i < j; i++, j--) {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  // Reverse the entire array  for (i = 0, j = n - 1; i < j; i++, j--) {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  } } int main() {  vector<int> arr = {1, 2, 3, 4, 5, 6};  int k = 2;  rotateclockwise(arr, k);   for (int i = 0; i < arr.size(); i++) {  cout << arr[i] << " ";  }  return 0; } 

import java.util.*; public class Main {  public static void rotateclockwise(int[] arr, int k) {  int n = arr.length;  if (n == 0) return;  k = k % n;  int i, j;  // Reverse last k elements  for (i = n - k, j = n - 1; i < j; i++, j--) {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  // Reverse first n-k elements  for (i = 0, j = n - k - 1; i < j; i++, j--) {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  // Reverse the entire array  for (i = 0, j = n - 1; i < j; i++, j--) {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  }  public static void main(String[] args) {  int[] arr = {1, 2, 3, 4, 5, 6};  int k = 2;   rotateclockwise(arr, k);   for (int it : arr) {  System.out.print(it + " ");  }  } } 

def rotateclockwise(arr, k): n = len(arr) if n == 0: return k = k % n # Reverse last k elements arr[n - k:] = reversed(arr[n - k:]) # Reverse first n-k elements arr[:n - k] = reversed(arr[:n - k]) # Reverse the entire array arr[:] = reversed(arr) # No return — modifies arr in-place if __name__ == "__main__": arr = [1, 2, 3, 4, 5, 6] k = 2 rotateclockwise(arr, k) for it in arr: print(it, end=" ") 

using System; class GfG{    static void rotateclockwise(int[] arr, int k){    int n = arr.Length;  if (n == 0) return;  k = k % n;  int i, j;  // Reverse last k elements  for (i = n - k, j = n - 1; i < j; i++, j--){    int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  // Reverse first n - k elements  for (i = 0, j = n - k - 1; i < j; i++, j--){    int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  // Reverse the entire array  for (i = 0, j = n - 1; i < j; i++, j--){    int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  }  static void Main(){    int[] arr = {1, 2, 3, 4, 5, 6};  int k = 2;   rotateclockwise(arr, k);  foreach (int it in arr){    Console.Write(it + " ");  }  } } 

function rotateclockwise(arr, k) {  const n = arr.length;  if (n === 0) return;  k = k % n;  // Reverse last k numbers  reverse(arr, n - k, n - 1);  // Reverse the first n-k terms  reverse(arr, 0, n - k - 1);  // Reverse the entire array  reverse(arr, 0, n - 1);  // No return — modifies arr in place } function reverse(arr, start, end) {  while (start < end) {  let temp = arr[start];  arr[start] = arr[end];  arr[end] = temp;  start++;  end--;  } } // Driver Code let arr = [1, 2, 3, 4, 5, 6]; let k = 2; rotateclockwise(arr, k);  console.log(arr.join(" ")); 

5 6 1 2 3 4