Rotate Array

“Rotate array” refers to the process of rearranging the elements within an array by shifting each element to a new position. This rearrangement can be performed either clockwise or counterclockwise.

Types of Array Rotation in Array

Right Rotation

In right rotation, the array elements are shifted towards the right. Each element moves to the position one step to the right, and the last element moves to the first position.

Left Rotation

In left rotation, the array elements are shifted towards the left. Each element moves to the position one step to the left, and the first element moves to the last position.

How to Implement Rotations in an Array?

1. Rotate One by One

• In this method array is rotated one by one k times.
• While rotating always store the first element in a temp array and shift rest of the elements by one step.
• Example – arr =[1,2,3,4,5,6] , k=2
  • rotate array by one step (left rotation) – arr = [2,3,4,5,6,1]
  • rotate array again by one step (left rotation) – arr=[3,4,5,6,1,2]

C++ Implementation (Rotate Array – C++)

#include <iostream> 
using namespace std; 
  
void rotate(int test_arr[], int n) 
{ 
    int x = test_arr[0]; 
    for(int i=1; i<n; i++){
        test_arr[i-1] = test_arr[i];
    }
    test_arr[n-1] = x; 
} 
  
// Driver code 
int main()  
{ 
    int test_arr[] = {1, 2, 3, 4, 5}, i; 
    int n = sizeof(test_arr) /  sizeof(test_arr[0]); 
  
    cout << "Given array is: \n"; 
    for (i = 0; i < n; i++) 
        cout << test_arr[i] << " ";
    cout << "\n";
    
    int k = 3;
    
    // rotating array one by one k times.
    for(int j=0; j<k; j++)
        rotate(test_arr, n); 
  
    cout << "Rotated array is: \n"; 
    for (i = 0; i < n; i++) 
        cout << test_arr[i] << " ";
    cout << "\n";

    return 0; 
}  

Java Implementation (Rotate Array – Java)

import java.util.Arrays; 
  
public class Main  
{ 
    static int test_arr[] = new int[]{1, 2, 3, 4, 5}; 
      
    // Method for rotation 
    static void rotate() 
    { 
        int x = test_arr[0]; 
        for(int i=1; i<test_arr.length; i++){
            test_arr[i-1] = test_arr[i];
        }
        test_arr[test_arr.length-1] = x; 
    } 
      
    public static void main(String[] args)  
    { 
        System.out.println("Given Array is"); 
        System.out.println(Arrays.toString(test_arr)); 
          
        rotate(); 
          
        System.out.println("Rotated Array is"); 
        System.out.println(Arrays.toString(test_arr)); 
    } 
} 

Python Implementation (Rotate Array – Python)

def rotate(test_arr, n): 
    x = test_arr[0] 
    for i in range(1, n):
        test_arr[i-1] = test_arr[i]
    test_arr[n-1] = x; 
  
test_arr= [1, 2, 3, 4, 5] 
n = len(test_arr) 
print("Given array is") 
print(*test_arr) 
  
rotate(test_arr, n) 
  
print ("Rotated array is") 
print(*test_arr)

Complexity Analysis

• Time Complexity – O(n)
• Space Complexity – O(n)

3. Juggling Algorithm

• This method is an extension of the Rotate array one by one method.
• In juggling algorithm, the given array is divided into different sets where number of sets is equal to GCD(n, k), where n is the length of array.
• The elements are then moved k positions to the left within the sets.
• Let’s take an example and see how juggling algorithm works – arr = [1,2,3,4,5,6,7,8,9,10,11,12] and k=3
• In the above example the length of the array n=12 and k=3. The GCD of 12 and 3 is 3.
• So, the array will be divided into 3 sets and the elements will be moved among the sets.

• After first step, elements are moved in first set as shown in the figure above. The array after first step will be [4 2 3 7 5 6 10 8 9 1 11 12]
• Similarly, After second set move – arr= [4 5 3 7 8 6 10 11 9 1 2 12]
• After third set move – arr= [4 5 6 7 8 9 10 11 12 1 2 3]

C++ Implementation (Rotate Array – C++)

#include <bits/stdc++.h>
using namespace std;

/*Function to get gcd of a and b*/
int gcd(int num1, int num2)
{
	if (num2 == 0)
		return num1;
	return gcd(num2, num1 % num2);
}

/*Function to left rotate arr[] of size n by k*/
void leftRotate(int test_arr[], int k, int n)
{
	/* To handle if k >= n */
	k = k % n;
	int Gcd = gcd(k, n);
	for (int i = 0; i < Gcd; i++) {
		/* Move each element by k position to the left within ith set */
		int temp = test_arr[i];
		int j = i;

		while (1) {
			int d = j + k;
			if (d >= n)
				d = d - n;

			if (d == i)
				break;

			test_arr[j] = test_arr[d];
			j = d;
		}
		test_arr[j] = temp;
	}
}

// Function to print an array
void printFullArray(int test_arr[], int n)
{
	for (int i = 0; i < n; i++)
		cout << test_arr[i] << " ";
}

/* Driver program to test above functions */
int main()
{
	int test_arr[] = { 1, 2, 3, 4, 5, 6, 7 };
    int k=5;
	int n = sizeof(test_arr) / sizeof(test_arr[0]);
	leftRotate(test_arr, k, n);
	printFullArray(test_arr, n);

	return 0;
}

Java Implementation (Rotate Array – Java)

class Main {
	void leftRotate(int test_arr[], int k, int n)
	{
		/* To handle if d >= n */
		k = k % n;
		int i, j, d, temp;
		int Gcd = gcd(k, n);
		for (i = 0; i <  Gcd; i++) {
			/* Move each element by k position to the left within ith set */
			temp = test_arr[i];
			j = i;
			while (true) {
				d = j + k;
				if (d >= n)
					d = d - n;
				if (d == i)
					break;
				test_arr[j] = test_arr[d];
				j = d;
			}
			test_arr[j] = temp;
		}
	}

	/*UTILITY FUNCTIONS*/

	/* function to print an array */
	void printFullArray(int test_arr[], int n)
	{
		for (int i = 0; i < n; i++)
			System.out.print(test_arr[i] + " ");
	}

	/*Function to get gcd of a and b*/
	int gcd(int num1, int num2)
	{
		if (num2 == 0)
			return num1;
		return gcd(num2, num1 % num2);
	}

	public static void main(String[] args)
	{
		Main rotate = new Main();
		int test_arr[] = { 1, 2, 3, 4, 5, 6, 7 };
		int k = 4;
		rotate.leftRotate(test_arr, k, 7);
		rotate.printFullArray(test_arr, 7);
	}
}

Python Implementation (Rotate Array – Python)

def leftRotate(test_arr, k, n):
	k = k % n
	Gcd = gcd(k, n)
	for i in range(Gcd):
		
		# Move each element by k position to the left within ith set
		temp = test_arr[i]
		j = i
		while 1:
			d = j + k
			if d >= n:
				d = d - n
			if d == i:
				break
			test_arr[j] = test_arr[d]
			j = d
		test_arr[j] = temp

# Function to get gcd of a and b
def gcd(num1, num2):
	if num2 == 0:
		return num1
	return gcd(num2, num1 % num2)

# Driver program to test above functions
test_arr = [1, 2, 3, 4, 5, 6, 7]
n = len(test_arr)
k = 4
leftRotate(test_arr, k, n)
print(*test_arr)

Complexity Analysis

• Time Complexity – O(n)
• Space Complexity – O(1)

4. The Reversal Algorithm

• By observing the pattern in the rotation of the array, it can be thought of to be made of two parts arr[0..K-1] and arr[k..n-1], where n= size of array.
• Reverse the arr[0...k-1]
• Reverse the arr[k...n-1]
• Reverse the whole array [0...n-1]
• Lets’s take an example – arr = [1,2,3,4,5,6,7],k=3, length of the arr(n) =7
• After reversing arr[0..k-1] we get – [3,2,1,4,5,6,7]
• After reversing arr[k..n-1] we get – [3,2,1,7,6,5,4]
• After reversing the whole arr[0...n-1] we get [4,5,6,7,1,2,3]

C++ Implementation (Rotate Array – C++)

#include <bits/stdc++.h>
using namespace std;

/* reverse arr[] from index s to e */
void reverse(int test_arr[], int s, int e)
{
	while (s < e) {
		int temp = test_arr[s];
		test_arr[s] = test_arr[e];
		test_arr[e] = temp;
		s++;
		e--;
	}
}

/*  left rotate arr[] of size n by k*/
void leftRotate(int test_arr[], int k, int n)
{
	if (k== 0)
		return;
	// if k>n
	k= k% n;

	reverse(test_arr, 0, k - 1);
	reverse(test_arr, k, n - 1);
	reverse(test_arr, 0, n - 1);
}

// Function to print full  array
void printFullArray(int test_arr[], int n)
{
	for (int i = 0; i < n; i++)
		cout << test_arr[i] << " ";
}


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

	leftRotate(test_arr, k, n);
	printFullArray(test_arr, n);

	return 0;
}

Java Implementation (Rotate Array – Java)

import java.io.*;

class Main {
	static void leftRotate(int test_arr[], int k)
	{
		if (k == 0)
			return;

		int n = test_arr.length;
		// if k>n
		k = k % n;
		reverse(test_arr, 0, k - 1);
		reverse(test_arr, k, n - 1);
		reverse(test_arr, 0, n - 1);
	}

	static void reverse(int test_arr[], int s, int e)
	{
		int temp;
		while (s < e) {
			temp = test_arr[s];
			test_arr[s] = test_arr[e];
			test_arr[e] = temp;
			s++;
			e--;
		}
	}

	static void printFullArray(int test_arr[])
	{
		for (int i = 0; i < test_arr.length; i++)
			System.out.print(test_arr[i] + " ");
	}

	public static void main(String[] args)
	{
		int test_arr[] = { 1, 2, 3, 4, 5, 6, 7 };
		int n = test_arr.length;
		int k = 5;

		leftRotate(test_arr, k); 
		printFullArray(test_arr);
	}
}

Python Implementation (Rotate Array – Python)

def leftRotateByK(test_arr, k):
    if k == 0:
        return
    n = len(test_arr)
    # if k>n
    k = k % n
    
    first_k_elements = test_arr[:k]
    remaining_elements = test_arr[k: ]
    new_arr = first_k_elements[::-1] + remaining_elements[::-1]
    return new_arr[::-1]

test_arr = [1, 2, 3, 4, 5, 6, 7]
n = len(test_arr)
k= 4

test_arr = leftRotateByK(test_arr, k)
print(*test_arr)

Complexity Analysis

• Time Complexity – O(n)
• Space Complexity – O(1)

Applications of Array Rotation

1. Search in a Sorted and Rotated Array: Efficiently searching in a sorted and rotated array can be achieved using algorithms like binary search, which capitalize on the rotation to find elements quickly.
2. Image Processing and Computer Vision: In image processing and computer vision applications, array rotations play a crucial role in tasks such as image transformation, alignment, registration, and feature detection, enabling various image manipulation and analysis techniques.
3. Text Editing and Processing: Text editing software utilizes array rotations for implementing text selection, deletion operations, as well as undo and redo functionalities, allowing users to manipulate and navigate through text efficiently.
4. Audio and Video Processing: Array rotation techniques are employed for applying effects like pitch shifting, time stretching, stereo panning, and creating dynamic visual effects.

Advantages of Rotations in an Array

1. Array rotation can optimize performance by enabling the use of more efficient algorithms or data structures for operations like searches or lookups. This optimization can lead to faster processing times and improved overall efficiency.
2. Array rotation simplifies computations, particularly in scenarios involving matrices. For example, rotating a matrix can streamline operations such as matrix-vector multiplication by facilitating the use of simpler computation methods like the dot product, thereby reducing complexity and enhancing computational efficiency.
3. By rotating an array, you can transform its representation, making it more adaptable and easier to work with or analyze. For instance, rotating a matrix can facilitate its representation as a vector or alter the orientation of the data, enhancing flexibility in data manipulation.

Some FAQs regarding Array Rotation

Q. What is Array Rotation?
A. Array rotation involves rearranging the elements of an array by shifting them to new positions either in a clockwise or counterclockwise direction.

Q. Is Array Rotation in place or takes extra space?
A. Array rotation can be executed in place, directly modifying the original array without requiring additional memory allocation. This in-place operation proves advantageous, especially in scenarios where minimizing memory usage is crucial.

Q. What is the Relation between Array Rotation and Modular Arithmetic?
A. Array rotation is closely related to modular arithmetic, as the modulo operation is used to calculate the new positions of array elements after rotation, demonstrating their integration.

Q. Can Array Rotation be Applied to Data Structures?
A. Yes, array rotation can be used to implement data structures like circular buffers and circular queues, where it facilitates pointer movement or element addition/removal.

Conclusion

• Rotate array operation can be done in many ways with different space and time complexity.
• Several methods such as rotating one element at a time, using temporary arrays, employing juggling algorithms, or employing reversal algorithms offer different approaches to array rotation.
• Depending on the implementation method, array rotation can be performed in-place, optimizing memory usage, and typically has time complexities ranging from O(n) to O(n*k), where n is the size of the array and k is the rotation count.
• Rotating arrays enables flexible data representation, simplifies computations, and optimizes performance by facilitating the use of faster algorithms or data structures, enhancing adaptability and ease of use.