YouTipPython3 Array Rotation
# Python 3 Program for Array Rotation
Array rotation is a fundamental algorithmic operation where elements of an array are shifted to the left or right by a specified number of positions.
In this tutorial, you will learn how to perform a **left rotation** on an array (or list) in Python. A left rotation shifts all elements to the left by $d$ positions, and the first $d$ elements are moved to the end of the array.
---
## Problem Description
Given an array of size $n$, rotate the array to the left by $d$ elements.
### Example
* **Input Array:** `[1, 2, 3, 4, 5, 6, 7]`
* **Rotation Factor ($d$):** `2`
* **Array Size ($n$):** `7`
#### Visual Representation:
**Original Array:**
```text
+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+
```
**After Left Rotating by 2 Elements:**
```text
+---+---+---+---+---+---+---+
| 3 | 4 | 5 | 6 | 7 | 1 | 2 |
+---+---+---+---+---+---+---+
```
---
## Method 1: Simple Rotation (Element-by-Element Shift)
This is the most straightforward approach. To rotate the array by $d$ elements, we shift the entire array to the left by one position, $d$ times.
### Algorithm
1. Store the first element in a temporary variable `temp`.
2. Shift all remaining elements one position to the left.
3. Place `temp` at the end of the array.
4. Repeat this process $d$ times.
### Python Implementation
```python
def leftRotate(arr, d, n):
# Rotate the array by one element d times
for i in range(d):
leftRotatebyOne(arr, n)
def leftRotatebyOne(arr, n):
# Store the first element
temp = arr
# Shift elements to the left
for i in range(n - 1):
arr = arr[i + 1]
# Put the first element at the end
arr = temp
def printArray(arr, size):
for i in range(size):
print("%d" % arr, end=" ")
# Test the implementation
arr = [1, 2, 3, 4, 5, 6, 7]
leftRotate(arr, 2, 7)
printArray(arr, 7)
```
### Output
```text
3 4 5 6 7 1 2
```
### Complexity Analysis
* **Time Complexity:** $O(n \times d)$ — Since we shift $n$ elements $d$ times.
* **Auxiliary Space:** $O(1)$ — No extra memory is used.
---
## Method 2: The Juggling Algorithm (Optimized Approach)
This is an optimized version of Method 1. Instead of moving elements one by one, we divide the array into different sets. The number of sets is equal to the Greatest Common Divisor (GCD) of $n$ and $d$.
### Algorithm
1. Find the GCD of $d$ and $n$.
2. Divide the array into $GCD(d, n)$ sets.
3. Shift elements within each set in a cyclic manner.
### Python Implementation
```python
def leftRotate(arr, d, n):
# Handle cases where d >= n
d = d % n
g_c_d = gcd(d, n)
for i in range(g_c_d):
# Move elements of the current set
temp = arr
j = i
while True:
k = j + d
if k >= n:
k = k - n
if k == i:
break
arr = arr
j = k
arr = temp
def printArray(arr, size):
for i in range(size):
print("%d" % arr, end=" ")
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# Test the implementation
arr = [1, 2, 3, 4, 5, 6, 7]
leftRotate(arr, 2, 7)
printArray(arr, 7)
```
### Output
```text
3 4 5 6 7 1 2
```
### Complexity Analysis
* **Time Complexity:** $O(n)$ — Every element is visited only once.
* **Auxiliary Space:** $O(1)$ — In-place rotation with no extra memory.
---
## Method 3: The Reversal Algorithm (Highly Recommended)
The Reversal Algorithm is elegant, easy to understand, and highly efficient. It works by reversing specific sub-segments of the array.
### Algorithm
To rotate an array of size $n$ by $d$ elements:
1. Reverse the first $d$ elements: `reverse(arr, 0, d-1)`
2. Reverse the remaining $n-d$ elements: `reverse(arr, d, n-1)`
3. Reverse the entire array: `reverse(arr, 0, n-1)`
#### Step-by-Step Example ($arr = [1, 2, 3, 4, 5, 6, 7], d = 2$):
* **Step 1 (Reverse first $d$ elements):** `[2, 1, 3, 4, 5, 6, 7]`
* **Step 2 (Reverse remaining elements):** `[2, 1, 7, 6, 5, 4, 3]`
* **Step 3 (Reverse the whole array):** `[3, 4, 5, 6, 7, 1, 2]`
### Python Implementation
```python
def reverseArray(arr, start, end):
# Helper function to reverse array in-place
while start < end:
temp = arr
arr = arr
arr = temp
start += 1
end -= 1
def leftRotate(arr, d):
n = len(arr)
# Handle cases where d is greater than array length
d = d % n
reverseArray(arr, 0, d - 1)
reverseArray(arr, d, n - 1)
reverseArray(arr, 0, n - 1)
def printArray(arr):
for i in range(0, len(arr)):
print(arr, end=' ')
# Test the implementation
arr = [1, 2, 3, 4, 5, 6, 7]
leftRotate(arr, 2)
printArray(arr)
```
### Output
```text
3 4 5 6 7 1 2
```
### Complexity Analysis
* **Time Complexity:** $O(n)$ — Two passes over the array elements.
* **Auxiliary Space:** $O(1)$ — In-place modification.
---
## Method 4: Pythonic Slicing (The Modern Way)
In real-world Python development, you can leverage Python's powerful list slicing syntax to perform array rotation in a single line of code.
### Python Implementation
```python
def leftRotateSlicing(arr, d):
n = len(arr)
d = d % n
# Slice from index d to end, and concatenate with slice from start to d
return arr[d:] + arr[:d]
# Test the implementation
arr = [1, 2, 3, 4, 5, 6, 7]
rotated_arr = leftRotateSlicing(arr, 2)
print(rotated_arr)
```
### Output
```text
[3, 4, 5, 6, 7, 1, 2]
```
### Complexity Analysis
* **Time Complexity:** $O(n)$ — Slicing and concatenation create a new list of size $n$.
* **Auxiliary Space:** $O(n)$ — Requires extra memory to store the newly created list.
---
## Summary & Comparison
| Method | Time Complexity | Auxiliary Space | In-Place | Best Used For |
| :--- | :--- | :--- | :--- | :--- |
| **Method 1: Simple Shift** | $O(n \times d)$ | $O(1)$ | Yes | Educational purposes only |
| **Method 2: Juggling** | $O(n)$ | $O(1)$ | Yes | Low-memory embedded systems |
| **Method 3: Reversal** | $O(n)$ | $O(1)$ | Yes | Standard coding interviews |
| **Method 4: Slicing** | $O(n)$ | $O(n)$ | No | Rapid application development in Python |