💡 Problem Formulation: In array rotation, elements of an array are moved by a number of positions in a particular direction. This article explores how to implement the reversal algorithm for rotating an array using Python. Given an input array, for instance [1, 2, 3, 4, 5, 6, 7], and a number of positions to rotate (k=2), the desired output after left rotation would be [3, 4, 5, 6, 7, 1, 2].
Method 1: Standard Reversal Algorithm
This method involves reversing parts of the array to accomplish the left rotation. First the entire array is reversed, then the two portions (0 to k-1 and k to end) are reversed individually. This method requires no additional memory space and operates in-place.
Here’s an example:
def rotate(arr, k):
n = len(arr)
arr[:k] = reversed(arr[:k])
arr[k:] = reversed(arr[k:])
arr.reverse()
# Example usage
arr = [1, 2, 3, 4, 5, 6, 7]
rotate(arr, 2)
print(arr)Output: [3, 4, 5, 6, 7, 1, 2]
The function rotate() initially reverses the first k elements, then the remaining elements, and finally the entire array. After these three reversals, we get the array rotated by k elements.
Method 2: Auxiliary Array
This method uses an auxiliary array to store the rotated version of the original array. We copy the last n-k elements followed by the first k elements into a new array. This method uses additional memory proportional to the size of the array.
Here’s an example:
def rotate(arr, k):
n = len(arr)
rotated_arr = arr[k:] + arr[:k]
return rotated_arr
# Example usage
arr = [1, 2, 3, 4, 5, 6, 7]
print(rotate(arr, 2))Output: [3, 4, 5, 6, 7, 1, 2]
The function rotate() slices the array and uses concatenation to create the rotated version, resulting in a new array.
Method 3: In-Place Rotation Using Python’s Slicing
This method takes advantage of Python’s slicing capabilities to rotate the array in place without using additional memory. We directly assign the array with its slices swapped.
Here’s an example:
def rotate(arr, k):
n = len(arr)
arr[:] = arr[k:] + arr[:k]
# Example usage
arr = [1, 2, 3, 4, 5, 6, 7]
rotate(arr, 2)
print(arr)Output: [3, 4, 5, 6, 7, 1, 2]
The function rotate() performs the rotation by swapping slices of the array, thus effectively rotating it without need for an extra array.
Method 4: Using Collections Module
Python’s collections module provides the deque data structure that can be used to rotate arrays efficiently using its rotate() method. This approach effectively handles rotation and utilizes Python’s built-in features.
Here’s an example:
from collections import deque
def rotate(arr, k):
d = deque(arr)
d.rotate(-k) # Negative value for left rotation
return list(d)
# Example usage
arr = [1, 2, 3, 4, 5, 6, 7]
print(rotate(arr, 2))Output: [3, 4, 5, 6, 7, 1, 2]
The function rotate() converts the array to a deque, uses the rotate method for left rotation, and then converts it back to a list.
Bonus One-Liner Method 5: List Comprehension with Modulo
Employing list comprehension and the modulo operator makes for a concise one-liner solution that follows Python’s philosophy of simplicity and readability.
Here’s an example:
# Example usage arr = [1, 2, 3, 4, 5, 6, 7] k = 2 print([(arr[(i + k) % len(arr)]) for i in range(len(arr))])
Output: [3, 4, 5, 6, 7, 1, 2]
This one-liner code uses list comprehension to create a new list that contains the rotated elements. The modulo operation ensures that the indices cycle through the array correctly.
Summary/Discussion
- Method 1: Standard Reversal Algorithm. Efficient in terms of space. Can be tricky to get right due to multiple reverse operations.
- Method 2: Auxiliary Array. Simple to understand and implement. Requires extra memory equal to the size of the array.
- Method 3: In-Place Rotation Using Python’s Slicing. Memory efficient and pythonic. May not be as clear to beginners as other methods.
- Method 4: Using Collections Module. Takes advantage of Python’s built-in data structures. Slightly less intuitive but very powerful and concise.
- Method 5: Bonus One-Liner with Modulo. Extremely concise and readable. Not as efficent as other methods and can be slow for large arrays due to its space complexity.