# Rotate elements in an Array Data Structure

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()
``````

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()
``````

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.

Refer to this article for more details on how this algorithm works.

Code

``````
# 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()
``````

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()
``````

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]`