Array rotation is the process of shifting all elements present in an array by a specified number of positions either to the left or to the right. To understand the concept of array rotation, it is helpful to think of an array as a circular structure i.e, imagine that all the elements in an array are laid out in a circle, rather than a straight line. Below is how you can visualize an array as a circular structure:
a[0], a[1], a[2] etc., are the first, second and third elements in the array respectively.
Rotate k positions to the left
Rotating array elements to the left means shifting each element k positions to the left, with the first k elements wrap around to become the last k elements. For example, after rotating 2 positions to the left, the example array we looked at before, transforms to the array shown below:
Notice that the first 2 elements in the array became the last 2 elements in the array after rotation and all the other elements are shifted by 2 positions to the left.
Note: If the value of k (the number of rotations) is equal to the array size or some multiple of array size, the rotated array will be the same as the original array. So if the value of k is more than the array size, we need to make (k % n) rotations. This ensures we only perform only the required number of rotations. For example, performing 4 rotations on array [1,2,3] is same as performing 1 rotation, the result will be [2,3,1].
Using a Temporary Array
This approach involves creating a temporary array to perform the rotation process and the result is finally copied back to the original array.
Algorithm
Calculate the number of actual rotations to be done using the equation k = k % n, where n is the size of the array.
Create a temporary array with the same size as the original array.
Copy elements from the original array to the temporary array, starting at index k until the last index.
Copy the remaining elements (if any) from the beginning of the original array (index 0 to k-1) to the end of the temporary array.
Finally, copy the contents of the temporary array back into the original array.
Example Scenario
Let’s consider the array [1, 2, 3, 4, 5] which needs to be rotated k:2 positions left
First create a temporary array with the same size as original array: [_, _, _, _, _]
Copy all elements from index k:2 till the ending of input array to the temporary array: [3, 4, 5, _, _]
Now copy remaining elements from start of input array until index k-1 to the temporary array: [3, 4, 5, 1, 2]
Finally copy the temporary array to original array.
Code
# Function to rotate the array
def rotate_array(arr, k):
# Calculate the actual number of rotations to be done
k = k % len(arr)
# Create a temporary array of the same size as the original array
temp_arr = [0] * len(arr)
# Initialize Index variable to track position in rotated array
ri = 0
# Copy elements from the original array to the temporary array
# starting from k to n-1 (the end of original array)
for i in range(k, len(arr)):
temp_arr[ri] = arr[i]
ri += 1
# Copy the elements from 0 to k-1th index in the original array
# to the end of rotated array
for i in range(k):
temp_arr[ri] = arr[i]
ri += 1
# Copy the contents of the temporary array back into the original array
for i in range(len(arr)):
arr[i] = temp_arr[i]
def main():
# Sample array
arr = [1, 2, 3, 4, 5]
k = 2
print("Array before rotation: ", arr)
# Call the rotateArray function
rotate_array(arr, k)
# Print the rotated array
print("Array after rotation: ", arr)
# Call the main function
main()
// Function to rotate the array
void rotateArray(int *arr, int n, int k) {
// Calculate the actual number of rotations to be done
k = k % n;
// Create a temporary array of the same size as the original array
int *temp_arr = (int *)malloc(n * sizeof(int));
// Initialize Index variable to track position in rotated array
int ri = 0;
// Copy elements from the original array to the temporary array
// starting from k to n-1 (the end of original array)
for (int i = k; i < n; i++) {
temp_arr[ri] = arr[i];
ri++;
}
// Copy the elements from 0 to k-1th index in the original array
// to the end of rotated array
for (int i = 0; i < k; i++) {
temp_arr[ri] = arr[i];
ri++;
}
// Copy the contents of the temporary array back into the original array
for (int i = 0; i < n; i++) {
arr[i] = temp_arr[i];
}
// Free the temporary array
free(temp_arr);
}
int main() {
// Sample array
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
printf("Array before rotation: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// Call the rotateArray function
rotateArray(arr, n, k);
// Print the rotated array
printf("Array after rotation: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
// Function to rotate the array
void rotateArray(std::vector<int>& arr, int k) {
// Calculate the actual number of rotations to be done
k = k % arr.size();
// Create a temporary array of the same size as the original array
std::vector<int> temp_arr(arr.size());
// Initialize Index variable to track position in rotated array
int ri = 0;
// Copy elements from the original array to the temporary array
// starting from k to n-1 (the end of original array)
for (int i = k; i < arr.size(); i++) {
temp_arr[ri] = arr[i];
ri++;
}
// Copy the elements from 0 to k-1th index in the original array
// to the end of rotated array
for (int i = 0; i < k; i++) {
temp_arr[ri] = arr[i];
ri++;
}
// Copy the contents of the temporary array back into the original array
for (int i = 0; i < arr.size(); i++) {
arr[i] = temp_arr[i];
}
}
int main() {
// Sample array
std::vector<int> arr = {1, 2, 3, 4, 5};
int k = 2;
std::cout << "Array before rotation: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
// Call the rotateArray function
rotateArray(arr, k);
// Print the rotated array
std::cout << "Array after rotation: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
// Function to rotate the array
function rotateArray(arr, k) {
// Calculate the actual number of rotations to be done
k = k % arr.length;
// Create a temporary array of the same size as the original array
let tempArr = new Array(arr.length).fill(0);
// Initialize Index variable to track position in rotated array
let ri = 0;
// Copy elements from the original array to the temporary array
// starting from k to n-1 (the end of original array)
for (let i = k; i < arr.length; i++) {
tempArr[ri] = arr[i];
ri++;
}
// Copy the elements from 0 to k-1th index in the original array
// to the end of rotated array
for (let i = 0; i < k; i++) {
tempArr[ri] = arr[i];
ri++;
}
// Copy the contents of the temporary array back into the original array
for (let i = 0; i < arr.length; i++) {
arr[i] = tempArr[i];
}
}
function main() {
// Sample array
let arr = [1, 2, 3, 4, 5];
let k = 2;
console.log("Array before rotation: ", arr);
// Call the rotateArray function
rotateArray(arr, k);
// Print the rotated array
console.log("Array after rotation: ", arr);
}
// Call the main function
main();
// Function to rotate the array
public static void rotateArray(int[] arr, int k) {
// Calculate the actual number of rotations to be done
k = k % arr.length;
// Create a temporary array of the same size as the original array
int[] tempArr = new int[arr.length];
// Initialize Index variable to track position in rotated array
int ri = 0;
// Copy elements from the original array to the temporary array
// starting from k to n-1 (the end of original array)
for (int i = k; i < arr.length; i++) {
tempArr[ri] = arr[i];
ri++;
}
// Copy the elements from 0 to k-1th index in the original array
// to the end of rotated array
for (int i = 0; i < k; i++) {
tempArr[ri] = arr[i];
ri++;
}
// Copy the contents of the temporary array back into the original array
for (int i = 0; i < arr.length; i++) {
arr[i] = tempArr[i];
}
}
public static void main(String[] args) {
// Sample array
int[] arr = {1, 2, 3, 4, 5};
int k = 2;
System.out.println("Array before rotation: " + Arrays.toString(arr));
// Call the rotateArray function
rotateArray(arr, k);
// Print the rotated array
System.out.println("Array after rotation: " + Arrays.toString(arr));
}
Time Complexity: O(n) – The algorithm iterates over the array elements twice, resulting in linear time complexity.
Space Complexity: O(n) – An extra temporary array is created, leading to O(n) space complexity.
IMPROVE_THIS: Add example section similar to the previous section to all the below sections
In-Place Rotation Using Element-by-Element Shifting
This method relies on shifting elements individually within the array.
Algorithm
Calculate the number of actual rotations to be done using the equation k = k % n, where n is the size of the array.
Repeat for the number of rotations (k):
Store the first element in a temporary variable.
Shift each remaining element one position to the left.
Place the stored element (from the temporary variable) at the end of the array.
Example Scenario
Let’s consider the array [1, 2, 3, 4, 5] which needs to be rotated k:2 positions left
Iteration-1:
Store first element 1 in a temporary variable
Shift all elements one position to the left: [2, 3, 4, 5, _]
Copy the first element to the end: [2, 3, 4, 5, 1]
Iteration-2:
Store first element 2 in a temporary variable
Shift all elements one position to the left: [3, 4, 5, 1, _]
Copy the first element to the end: [3, 4, 5, 1, 2]
Final rotated array: [3, 4, 5, 1, 2]
Code
def rotate_array(arr, k):
"""
Function to rotate the array k times to the left
Args:
arr (list): The input array to be rotated
k (int): The number of times to rotate the array towards left
"""
# Calculate the number of actual rotations to be done
k = k % len(arr)
# In each iteration, we rotate array by 1 position to left
# And repeat the iteration for k times
for i in range(k):
# Store the first element in a temporary variable
temp = arr[0]
# Shift each remaining element one position to the left
for j in range(len(arr) - 1):
arr[j] = arr[j+1]
# Place the stored element (from the temporary variable) at the end of the array
arr[len(arr)-1] = temp
def main():
"""
Main function to test the rotate_array function
"""
# Sample array
arr = [1, 2, 3, 4, 5]
k = 2
print("Array before rotation:", arr)
# Call the rotate_array function
rotate_array(arr, k)
# Print the rotated array
print("Array after rotation:", arr)
# Call the main function
if __name__ == "__main__":
main()
// Function to rotate the array k times to the left
void rotateArray(int *arr, int n, int k) {
// Calculate the number of actual rotations to be done
k = k % n;
// In each iteration, we rotate array by 1 position to left
// And repeat the iteration for k times
for (int i = 0; i < k; i++) {
// Store the first element in a temporary variable
int temp = arr[0];
// Shift each remaining element one position to the left
for (int j = 0; j < n - 1; j++) {
arr[j] = arr[j + 1];
}
// Place the stored element (from the temporary variable) at the end of the array
arr[n - 1] = temp;
}
}
int main() {
// Sample array
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
printf("Array before rotation: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// Call the rotateArray function
rotateArray(arr, n, k);
// Print the rotated array
printf("Array after rotation: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
// Function to rotate the array k times to the left
void rotateArray(std::vector<int>& arr, int k) {
// Calculate the number of actual rotations to be done
k = k % arr.size();
// In each iteration, we rotate array by 1 position to left
// And repeat the iteration for k times
for (int i = 0; i < k; i++) {
// Store the first element in a temporary variable
int temp = arr[0];
// Shift each remaining element one position to the left
for (int j = 0; j < arr.size() - 1; j++) {
arr[j] = arr[j + 1];
}
// Place the stored element (from the temporary variable) at the end of the array
arr[arr.size() - 1] = temp;
}
}
int main() {
// Sample array
std::vector<int> arr = {1, 2, 3, 4, 5};
int k = 2;
std::cout << "Array before rotation: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
// Call the rotateArray function
rotateArray(arr, k);
// Print the rotated array
std::cout << "Array after rotation: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
// Function to rotate the array k times to the left
function rotateArray(arr, k) {
// Calculate the number of actual rotations to be done
k = k % arr.length;
// In each iteration, we rotate array by 1 position to left
// And repeat the iteration for k times
for (let i = 0; i < k; i++) {
// Store the first element in a temporary variable
let temp = arr[0];
// Shift each remaining element one position to the left
for (let j = 0; j < arr.length - 1; j++) {
arr[j] = arr[j + 1];
}
// Place the stored element (from the temporary variable) at the end of the array
arr[arr.length - 1] = temp;
}
}
function main() {
// Sample array
let arr = [1, 2, 3, 4, 5];
let k = 2;
console.log("Array before rotation: ", arr);
// Call the rotateArray function
rotateArray(arr, k);
// Print the rotated array
console.log("Array after rotation: ", arr);
}
// Call the main function
main();
// Function to rotate the array k times to the left
public static void rotateArray(int[] arr, int k) {
// Calculate the number of actual rotations to be done
k = k % arr.length;
// In each iteration, we rotate array by 1 position to left
// And repeat the iteration for k times
for (int i = 0; i < k; i++) {
// Store the first element in a temporary variable
int temp = arr[0];
// Shift each remaining element one position to the left
for (int j = 0; j < arr.length - 1; j++) {
arr[j] = arr[j + 1];
}
// Place the stored element (from the temporary variable) at the end of the array
arr[arr.length - 1] = temp;
}
}
public static void main(String[] args) {
// Sample array
int[] arr = {1, 2, 3, 4, 5};
int k = 2;
System.out.println("Array before rotation: " + Arrays.toString(arr));
// Call the rotateArray function
rotateArray(arr, k);
// Print the rotated array
System.out.println("Array after rotation: " + Arrays.toString(arr));
}
Time Complexity: O(n * k) – The shifting operation occurs within a loop that runs k times, and each shift takes O(n) time.
Space Complexity: O(1) – The algorithm uses a single temporary variable, ensuring constant space complexity.
Juggling Algorithm (Dolphin Algorithm)
This algorithm is based on the concept of greatest common divisor (GCD) and involves a more optimized approach.
Algorithm
Calculate the number of actual rotations to be done using the equation k = k % n, where n is the size of the array.
Compute the GCD of the array size (n) and the number of rotations (k).
Divide the array into sets of size GCD.
Store element in the first set in a temporary variable.
For each set, iteratively swap element in the current set with the element in the next set at distance k.
If the next set’s index is more than size of array, we need to wrap the index to the beginning of array by computing (j+k) % arr_size
Stop when we reach the last set (When the next set is where we started)
Replace value in the last set with the value in the first set stored in temporary variable.
# Function to calculate the GCD of two numbers
def compute_gcd(a, b):
while b != 0:
a, b = b, a % b
return a
# Function to rotate an array by k positions
def rotate_array(arr, k):
# Calculate the number of actual rotations to be done
k = k % len(arr)
# Compute the GCD of (the array size and the number of rotations)
gcd = compute_gcd(len(arr), k)
# Divide the array into sets of size GCD
for i in range(gcd):
# Save the starting element of the current set in a temp variable
temp = arr[i]
# Iteratively swap elements between two sets at distance k
# Until we get back to the first set
j = i
while True:
# Compute index of element to shift in next set at distance k
# Wrap the index to beginning if it goes beyond end element
next_index = (j + k) % len(arr)
# Stop when the next set is the starting set
if next_index == i:
break
# Shift element in the next set to the current set
arr[j] = arr[next_index]
j = next_index
# Copy the starting element to the last set
arr[j] = temp
return arr
def main():
# Sample array
arr = [1, 2, 3, 4, 5]
k = 2
print("Array before rotation: ", arr)
# Call the rotateArray function
rotate_array(arr, k)
# Print the rotated array
print("Array after rotation: ", arr)
# Call the main function
main()
#include <stdio.h>
// Function to calculate the GCD of two numbers
int compute_gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// Function to rotate an array by k positions
void rotate_array(int arr[], int size, int k) {
// Calculate the number of actual rotations to be done
k = k % size;
// Compute the GCD of (the array size and the number of rotations)
int gcd = compute_gcd(size, k);
// Divide the array into sets of size GCD
for (int i = 0; i < gcd; i++) {
// Save the starting element of the current set in a temp variable
int temp = arr[i];
// Iteratively swap elements between two sets at distance k
// Until we get back to the first set
int j = i;
while (1) {
// Compute index of element to shift in next set at distance k
// Wrap the index to beginning if it goes beyond end element
int next_index = (j + k) % size;
// Stop when the next set is the starting set
if (next_index == i)
break;
// Shift element in the next set to the current set
arr[j] = arr[next_index];
j = next_index;
}
// Copy the starting element to the last set
arr[j] = temp;
}
}
int main() {
// Sample array
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 2;
printf("Array before rotation: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// Call the rotate_array function
rotate_array(arr, size, k);
printf("Array after rotation: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
#include <iostream>
#include <vector>
// Function to calculate the GCD of two numbers
int compute_gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// Function to rotate an array by k positions
std::vector<int> rotate_array(std::vector<int> arr, int k) {
// Calculate the number of actual rotations to be done
k = k % arr.size();
// Compute the GCD of (the array size and the number of rotations)
int gcd = compute_gcd(arr.size(), k);
// Divide the array into sets of size GCD
for (int i = 0; i < gcd; i++) {
// Save the starting element of the current set in a temp variable
int temp = arr[i];
// Iteratively swap elements between two sets at distance k
// Until we get back to the first set
int j = i;
while (true) {
// Compute index of element to shift in next set at distance k
// Wrap the index to beginning if it goes beyond end element
int next_index = (j + k) % arr.size();
// Stop when the next set is the starting set
if (next_index == i)
break;
// Shift element in the next set to the current set
arr[j] = arr[next_index];
j = next_index;
}
// Copy the starting element to the last set
arr[j] = temp;
}
return arr;
}
int main() {
// Sample array
std::vector<int> arr = {1, 2, 3, 4, 5};
int k = 2;
std::cout << "Array before rotation: ";
for (int num : arr)
std::cout << num << " ";
std::cout << std::endl;
// Call the rotateArray function
arr = rotate_array(arr, k);
// Print the rotated array
std::cout << "Array after rotation: ";
for (int num : arr)
std::cout << num << " ";
std::cout << std::endl;
return 0;
}
// Function to calculate the GCD of two numbers
function computeGcd(a, b) {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
// Function to rotate an array by k positions
function rotateArray(arr, k) {
// Calculate the number of actual rotations to be done
k = k % arr.length;
// Compute the GCD of (the array size and the number of rotations)
const gcd = computeGcd(arr.length, k);
// Divide the array into sets of size GCD
for (let i = 0; i < gcd; i++) {
// Save the starting element of the current set in a temp variable
let temp = arr[i];
// Iteratively swap elements between two sets at distance k
// Until we get back to the first set
let j = i;
while (true) {
// Compute index of element to shift in next set at distance k
// Wrap the index to beginning if it goes beyond end element
const nextIndex = (j + k) % arr.length;
// Stop when the next set is the starting set
if (nextIndex === i) {
break;
}
// Shift element in the next set to the current set
arr[j] = arr[nextIndex];
j = nextIndex;
}
// Copy the starting element to the last set
arr[j] = temp;
}
return arr;
}
function main() {
// Sample array
const arr = [1, 2, 3, 4, 5];
const k = 2;
console.log("Array before rotation: ", arr);
// Call the rotateArray function
rotateArray(arr, k);
// Print the rotated array
console.log("Array after rotation: ", arr);
}
// Call the main function
main();
import java.util.Arrays;
public class ArrayRotation {
// Function to calculate the GCD of two numbers
private static int computeGcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// Function to rotate an array by k positions
public static void rotateArray(int[] arr, int k) {
// Calculate the number of actual rotations to be done
k = k % arr.length;
// Compute the GCD of (the array size and the number of rotations)
int gcd = computeGcd(arr.length, k);
// Divide the array into sets of size GCD
for (int i = 0; i < gcd; i++) {
// Save the starting element of the current set in a temp variable
int temp = arr[i];
// Iteratively swap elements between two sets at distance k
// Until we get back to the first set
int j = i;
while (true) {
// Compute index of element to shift in next set at distance k
// Wrap the index to beginning if it goes beyond end element
int nextIndex = (j + k) % arr.length;
// Stop when the next set is the starting set
if (nextIndex == i) {
break;
}
// Shift element in the next set to the current set
arr[j] = arr[nextIndex];
j = nextIndex;
}
// Copy the starting element to the last set
arr[j] = temp;
}
}
public static void main(String[] args) {
// Sample array
int[] arr = {1, 2, 3, 4, 5};
int k = 2;
System.out.println("Array before rotation: " + Arrays.toString(arr));
// Call the rotateArray function
rotateArray(arr, k);
// Print the rotated array
System.out.println("Array after rotation: " + Arrays.toString(arr));
}
}
Time Complexity: O(n) – While there are nested loops, all elements are touched only once, leading to linear time complexity.
Space Complexity: O(1) – No additional data structures are used, resulting in constant space complexity.
Block Swap Algorithm
This efficient method rotates the array by reversing specific sections.
Algorithm
Calculate the number of actual rotations to be done using the equation k = k % n, where n is the size of the array.
Reverse the first block of elements from index 0 to k-1.
Reverse the second block of elements from index k to n-1.
Reverse the entire array to obtain the final rotated array.
Example Scenario
Let’s consider the array [1, 2, 3, 4, 5] which needs to be rotated k:2 positions left
Reverse the first block of elements from index 0 to k-1 = 2-1 = 1: [2, 1, 3, 4, 5]
Reverse the second block of elements from index k till the end of array: [2, 1, 5, 4, 3]
Reverse the entire array to obtain the final sorted array: [3, 4, 5, 1, 2]
Code
# Function to rotate the array k positions left
def rotate_array(arr, k):
# Calculate the actual number of rotations to be done
k = k % len(arr)
# Reverse the first block of elements from index 0 to k-1
reverse_array(arr, 0, k-1)
# Reverse the second block of elements from index k to n-1
reverse_array(arr, k, len(arr)-1)
# Reverse the entire array to obtain the final rotated array
reverse_array(arr, 0, len(arr)-1)
# Return the rotated array
return arr
# Function to reverse a subarray within the given range
def reverse_array(arr, start, end):
# Swap all elements including and between start and end indices
while start < end:
temp = arr[start]
arr[start] = arr[end]
arr[end] = temp
start += 1
end -= 1
def main():
# Sample array
arr = [1, 2, 3, 4, 5]
# Number of rotations
k = 2
print("Array before rotation: ", arr)
# Call the rotateArray function
rotate_array(arr, k)
# Print the rotated array
print("Array after rotation: ", arr)
# Call the main function
main()
#include <stdio.h>
#include <stdlib.h>
// Function to reverse a subarray within the given range
void reverseArray(int *arr, int start, int end) {
// Swap all elements including and between start and end indices
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
// Function to rotate the array k positions left
void rotateArray(int *arr, int n, int k) {
// Calculate the actual number of rotations to be done
k = k % n;
// Reverse the first block of elements from index 0 to k-1
reverseArray(arr, 0, k - 1);
// Reverse the second block of elements from index k to n-1
reverseArray(arr, k, n - 1);
// Reverse the entire array to obtain the final rotated array
reverseArray(arr, 0, n - 1);
}
int main() {
// Sample array
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
// Number of rotations
int k = 2;
printf("Array before rotation: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// Call the rotateArray function
rotateArray(arr, n, k);
printf("Array after rotation: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
// Function to rotate the array k positions left
void rotateArray(std::vector<int>& arr, int k) {
// Calculate the actual number of rotations to be done
k = k % arr.size();
// Reverse the first block of elements from index 0 to k-1
reverseArray(arr, 0, k-1);
// Reverse the second block of elements from index k to n-1
reverseArray(arr, k, arr.size()-1);
// Reverse the entire array to obtain the final rotated array
reverseArray(arr, 0, arr.size()-1);
}
// Function to reverse a subarray within the given range
void reverseArray(std::vector<int>& arr, int start, int end) {
// Swap all elements including and between start and end indices
while (start < end) {
std::swap(arr[start], arr[end]);
start++;
end--;
}
}
int main() {
// Sample array
std::vector<int> arr = {1, 2, 3, 4, 5};
// Number of rotations
int k = 2;
std::cout << "Array before rotation: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
// Call the rotateArray function
rotateArray(arr, k);
std::cout << "Array after rotation: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
// Function to rotate the array k positions left
function rotateArray(arr, k) {
// Calculate the actual number of rotations to be done
k = k % arr.length;
// Reverse the first block of elements from index 0 to k-1
reverseArray(arr, 0, k - 1);
// Reverse the second block of elements from index k to n-1
reverseArray(arr, k, arr.length - 1);
// Reverse the entire array to obtain the final rotated array
reverseArray(arr, 0, arr.length - 1);
// Return the rotated array
return arr;
}
// Function to reverse a subarray within the given range
function reverseArray(arr, start, end) {
// Swap all elements including and between start and end indices
while (start < end) {
[arr[start], arr[end]] = [arr[end], arr[start]];
start += 1;
end -= 1;
}
}
function main() {
// Sample array
const arr = [1, 2, 3, 4, 5];
// Number of rotations
const k = 2;
console.log("Array before rotation: ", arr);
// Call the rotateArray function
rotateArray(arr, k);
// Print the rotated array
console.log("Array after rotation: ", arr);
}
// Call the main function
main();
// Function to rotate the array k positions left
public static int[] rotateArray(int[] arr, int k) {
// Calculate the actual number of rotations to be done
k = k % arr.length;
// Reverse the first block of elements from index 0 to k-1
reverseArray(arr, 0, k-1);
// Reverse the second block of elements from index k to n-1
reverseArray(arr, k, arr.length-1);
// Reverse the entire array to obtain the final rotated array
reverseArray(arr, 0, arr.length-1);
// Return the rotated array
return arr;
}
// Function to reverse a subarray within the given range
public static void reverseArray(int[] arr, int start, int end) {
// Swap all elements including and between start and end indices
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
public static void main(String[] args) {
// Sample array
int[] arr = {1, 2, 3, 4, 5};
// Number of rotations
int k = 2;
System.out.println("Array before rotation: " + Arrays.toString(arr));
// Call the rotateArray function
rotateArray(arr, k);
// Print the rotated array
System.out.println("Array after rotation: " + Arrays.toString(arr));
}
Time Complexity: O(n) – Array reversals operate in linear time.
Space Complexity: O(1) – The reversals are performed in-place, offering constant space complexity.
Rotate k positions to the right
Rotating array elements to the right means shifting each element k positions to the right, with the last k elements wrapping around to become the first k elements. For example, after rotating 2 positions to the right, the same sample array would transform as shown below:
Notice that the last 2 elements of the array became the first 2 elements of the array after rotation and all the other elements are shifted by 2 positions to the right.
Note: Just like with rotations to the left, if k (the number of rotations) is equal to the array size or some multiple of the array size, the rotated array will be identical to the original array. To avoid redundant rotations, consider the remainder after dividing k by the array size (n) as the effective number of rotations: k = k % n.
Rotating k positions to the right is equivalent to rotating n - k positions to the left (where n is the size of the array). Since the algorithm for rotating k positions to the left is much clean and simpler, you can use any of the algorithms described in the “Rotate k positions to the left” section and simply substitute k with n - k to achieve a right/clockwise rotation.
Example:
Array: [1, 2, 3, 4, 5]
After rotating 2 positions to the right (k = 2), the array becomes: [4, 5, 1, 2, 3]
We can achieve the same by rotating 3 positions to the left (n - k = 5 - 2 = 3): [4, 5, 1, 2, 3]
