Rotate Array by K Elements

Problem Statement

Given an array of integers, rotating array of elements by k elements either left or right.

Examples:

Example 1:

Input: N = 5, array[] = {1, 2, 3, 4, 5}, k = 2, right

Output: 4, 5, 1, 2, 3

Example 2:

Input: N = 7, array[] = {1, 2, 3, 4, 5, 6, 7}, k = 3, left

Output: 4, 5, 6, 7, 1, 2, 3

Different Approaches

1 Approach (Using a temp array)

For Rotating the Elements to right

• Copy the last k elements into the temp array.
• Shift n-k elements from the beginning by k position to right.
• Copy the elements into the main array from the temp array.

Code:

#include <iostream>
using namespace std;

// Function to rotate elements of the array to the right by K positions
void Rotatetoright(int arr[], int n, int k) {
  // If array size is 0, return
  if (n == 0)
    return;

  // Calculate the effective rotation (reduce k to be less than n)
  k = k % n;

  // If rotation value is greater than array size, return
  if (k > n)
    return;

  // Temporary array to store elements to be rotated
  int temp[k];

  // Store the last k elements in the temporary array
  for (int i = n - k; i < n; i++) {
    temp[i - n + k] = arr[i];
  }

  // Shift elements to the right to make space for rotated elements
  for (int i = n - k - 1; i >= 0; i--) {
    arr[i + k] = arr[i];
  }

  // Copy elements from the temporary array to the beginning of the array
  for (int i = 0; i < k; i++) {
    arr[i] = temp[i];
  }
}

int main() {
  int n = 7;
  int arr[] = {1, 2, 3, 4, 5, 6, 7};
  int k = 2;

  // Call the function to rotate elements to the right by K positions
  Rotatetoright(arr, n, k);

  // Print the array after rotation
  cout << "After Rotating the elements to the right:" << endl;
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }

  return 0;
}

// Output
After Rotating the elements to the right:
6 7 1 2 3 4 5 

For Rotating the Elements to left

• Copy the first k elements into the temp array.
• Shift n-k elements from last by k position to the left.
• Copy the elements into the main array from the temp array.

Code:

#include <iostream>
using namespace std;

// Function to rotate elements of the array to the left by K positions
void Rotatetoleft(int arr[], int n, int k) {
  // If array size is 0, return
  if (n == 0)
    return;

  // Calculate the effective rotation (reduce k to be less than n)
  k = k % n;

  // If rotation value is greater than array size, return
  if (k > n)
    return;

  // Temporary array to store elements to be rotated
  int temp[k];

  // Store the first k elements in the temporary array
  for (int i = 0; i < k; i++) {
    temp[i] = arr[i];
  }

  // Shift elements to the left to make space for rotated elements
  for (int i = 0; i < n - k; i++) {
    arr[i] = arr[i + k];
  }

  // Copy elements from the temporary array to the end of the array
  for (int i = n - k; i < n; i++) {
    arr[i] = temp[i - n + k];
  }
}

int main() {
  int n = 7;
  int arr[] = {1, 2, 3, 4, 5, 6, 7};
  int k = 2;

  // Call the function to rotate elements to the left by K positions
  Rotatetoleft(arr, n, k);

  // Print the array after rotation
  cout << "After Rotating the elements to the left:" << endl;
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }

  return 0;
}


// Output
After Rotating the elements to the left:
3 4 5 6 7 1 2 

Complexity Analysis:

Time Complexity: O(n)

Space Complexity: O(k) since k array element needs to be stored in temp array.

2 Approach Second: Using Reversal Algorithm

For Rotating Elements to Right

• Reverse the last k elements of the array
• Reverse the first n-k elements of the array
• Reverse the whole array.

For Rotating Elements to Left

• Reverse the first k elements.
• Reverse the remaining elements.
• Reverse the entire array.

Code:

#include <iostream>
#include <algorithm> // For std::reverse
#include <vector>
using namespace std;

void leftRotate(vector<int>& arr, int k) {
    int n = arr.size();
    k = k % n;
    reverse(arr.begin(), arr.begin() + k);
    reverse(arr.begin() + k, arr.end());
    reverse(arr.begin(), arr.end());
}

void rightRotate(vector<int>& arr, int k) {
    int n = arr.size();
    k = k % n;
    reverse(arr.begin(), arr.end());
    reverse(arr.begin(), arr.begin() + k);
    reverse(arr.begin() + k, arr.end());
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    int k = 2;

    leftRotate(arr, k);
    cout << "Array after left rotation: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    rightRotate(arr, k);
    cout << "Array after right rotation: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    return 0;
}

Complexity Analysis

Time Complexity:

• Reversing the n-k and k elements, Both have a time complexity of (O(N-K)/2) and O(K/2), respectively, which simplifies to O(N-K) and O(K).
• Reversing the entire array: reversing the entire array involves traversing half of the array and swapping elements. This operation has a time complexity of O(N/2), which simplifies to O(N), where N is the number of elements in the array.
• Therefore, the overall time complexity is O(N) since the dominating term is linear

Space Complexity:

• It modifies the input array without requiring additional space. Hence, the time complexity is O(1)