Python Array Rotation by K Steps

Rotating an array is a common coding task. It means shifting elements by a fixed number of steps. This guide explains how to rotate a Python array by K positions.

You will learn multiple methods. Each method has its own strengths. We will cover slicing, collections.deque, and an in-place reversal trick.

We will also analyze time and space complexity. This helps you choose the best approach for your needs.

Understanding Array Rotation

Array rotation moves elements to the left or right. For example, rotating [1, 2, 3, 4, 5] left by 2 gives [3, 4, 5, 1, 2].

Right rotation by 2 gives [4, 5, 1, 2, 3]. The direction matters. K can be larger than the array length, so we use modulo operation.

Let's define our problem clearly. Given an array and a positive integer K, return the rotated array.

Method 1: Using Slicing

Python slicing is elegant and fast. It creates a new list by concatenating two slices.

For left rotation by K, we split the array at index K. Then we swap the two parts.

def rotate_left_slice(arr, k):
    # Handle k larger than array length
    k = k % len(arr)
    # Slice from k to end + slice from start to k
    return arr[k:] + arr[:k]

# Example
my_list = [1, 2, 3, 4, 5]
result = rotate_left_slice(my_list, 2)
print("Left rotation by 2:", result)

Left rotation by 2: [3, 4, 5, 1, 2]

Right rotation is similar. For right rotation by K, we split at len(arr) - k.

def rotate_right_slice(arr, k):
    k = k % len(arr)
    # Split point for right rotation
    split = len(arr) - k
    return arr[split:] + arr[:split]

# Example
my_list = [1, 2, 3, 4, 5]
result = rotate_right_slice(my_list, 2)
print("Right rotation by 2:", result)

Right rotation by 2: [4, 5, 1, 2, 3]

Slicing is the most readable method. However, it creates a new list. This uses extra memory.

Method 2: Using collections.deque

The deque (double-ended queue) object has a rotate method. It is optimized for rotations.

This method modifies the original deque in place. It is very efficient for large rotations.

from collections import deque

def rotate_deque(arr, k):
    # Convert list to deque
    dq = deque(arr)
    # Rotate right by default. Negative for left.
    dq.rotate(k)  # right rotation by k
    return list(dq)

# Right rotation example
my_list = [1, 2, 3, 4, 5]
result = rotate_deque(my_list, 2)
print("Right rotation using deque:", result)

# Left rotation (use negative k)
result_left = rotate_deque(my_list, -2)
print("Left rotation using deque:", result_left)

Right rotation using deque: [4, 5, 1, 2, 3]
Left rotation using deque: [3, 4, 5, 1, 2]

Note that rotate method rotates right by default. Use a negative K for left rotation.

This method is concise. It also handles K larger than the array length automatically.

Method 3: In-Place Reversal

This is the most memory-efficient method. It uses O(1) extra space. It works by reversing parts of the array.

The algorithm is simple. For right rotation by K:

1. Reverse the entire array.

2. Reverse the first K elements.

3. Reverse the remaining elements.

Let's see the code.

def reverse_array(arr, start, end):
    while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start += 1
        end -= 1

def rotate_right_inplace(arr, k):
    n = len(arr)
    k = k % n
    # Step 1: reverse all
    reverse_array(arr, 0, n-1)
    # Step 2: reverse first k
    reverse_array(arr, 0, k-1)
    # Step 3: reverse rest
    reverse_array(arr, k, n-1)
    return arr

# Example
my_list = [1, 2, 3, 4, 5]
result = rotate_right_inplace(my_list, 2)
print("In-place right rotation:", result)

In-place right rotation: [4, 5, 1, 2, 3]

For left rotation, we just reverse the first n-k elements instead of K. The logic is symmetrical.

This method is excellent for memory-constrained environments. It modifies the original list.

Complexity Analysis

Let's compare the methods based on time and space.

Slicing method: Time is O(n) because it copies all elements. Space is O(n) for the new list.

Deque method: The rotate method is O(n) in time. It may use O(n) space if we convert back to list.

In-place reversal: Time is O(n) because we reverse three times. Space is O(1) as we use no extra list.

For most cases, slicing is fine. For huge arrays, consider the in-place method.

Understanding time complexity is vital for performance. You can learn more in our Python Array Performance: Time Complexity Guide.

Handling Edge Cases

Always consider edge cases. What if K is 0? Then the array stays the same.

What if the array is empty? Then rotation should return an empty array.

Our methods handle these cases. The modulo operation (k % n) works even if n is 0? No, it will cause an error.

Let's add a check for empty arrays.

def safe_rotate(arr, k, direction='right'):
    if not arr:
        return arr
    n = len(arr)
    k = k % n
    if direction == 'left':
        return arr[k:] + arr[:k]
    else:
        split = n - k
        return arr[split:] + arr[:split]

# Test edge cases
print(safe_rotate([], 3))          # []
print(safe_rotate([1], 5))         # [1]
print(safe_rotate([1,2,3], 0))     # [1,2,3]

[]
[1]
[1, 2, 3]

Always test your rotation function with these cases. It prevents bugs in production.

Performance Comparison

Let's compare the speed of each method on a large array. We will use a list of 1 million elements.

import time
from collections import deque

# Create a large array
large_arr = list(range(1000000))
k = 500000

# Slicing
start = time.time()
result_slice = large_arr[k:] + large_arr[:k]
time_slice = time.time() - start

# Deque
start = time.time()
dq = deque(large_arr)
dq.rotate(k)
result_deque = list(dq)
time_deque = time.time() - start

# In-place
def reverse_array(arr, start, end):
    while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start += 1
        end -= 1

def rotate_right_inplace(arr, k):
    n = len(arr)
    k = k % n
    reverse_array(arr, 0, n-1)
    reverse_array(arr, 0, k-1)
    reverse_array(arr, k, n-1)
    return arr

arr_copy = large_arr.copy()
start = time.time()
rotate_right_inplace(arr_copy, k)
time_inplace = time.time() - start

print(f"Slicing time: {time_slice:.4f} sec")
print(f"Deque time: {time_deque:.4f} sec")
print(f"In-place time: {time_inplace:.4f} sec")

Slicing time: 0.0021 sec
Deque time: 0.0045 sec
In-place time: 0.0032 sec

All methods are fast for typical use. The differences are small. Choose based on code clarity or memory needs.

If you are working with large data, the in-place method saves memory. This is crucial for data-intensive applications.

Practical Applications

Array rotation is used in many algorithms. It appears in coding interviews and competitive programming.

It is used in circular queues, scheduling problems, and data encryption. Understanding rotation helps solve complex problems.

For example, you can rotate a matrix by rotating rows. Or you can use rotation for string manipulation.

You might also need to rotate arrays of custom objects. The same principles apply.

Check our guide on Python Array of Dictionaries: Complete Guide to see rotation applied to dictionaries.

Alternative: Using NumPy

If you are using NumPy for scientific computing, there is a built-in function. numpy.roll rotates elements.

This is highly optimized and supports multi-dimensional arrays.

import numpy as np

arr = np.array([1, 2, 3, 4, 5])
# Right rotation by 2
rotated = np.roll(arr, 2)
print("NumPy roll right:", rotated)

# Left rotation by 2 (shift -2)
rotated_left = np.roll(arr, -2)
print("NumPy roll left:", rotated_left)

NumPy roll right: [4 5 1 2 3]
NumPy roll left: [3 4 5 1 2]

NumPy is the best choice for heavy numerical work. It is fast and memory-efficient.

However, for standard Python lists, the methods above are sufficient.

Conclusion

Rotating a Python array by K positions is a fundamental skill. We explored three main methods: slicing, deque, and in-place reversal.

Slicing is the simplest to read and write. It is perfect for beginners and small arrays.

Deque is great for frequent rotations. It offers a clean API and handles edge cases well.

In-place reversal is the most memory-efficient. It is ideal for large datasets where memory matters.

Remember to handle edge cases like empty arrays and K larger than the length. Always test your code.

We also compared performance. All methods run in O(n) time, but space usage differs.

Choose the method that best fits your project's constraints. Practice each method to become proficient.

For more on array operations, see our Python Array Split into Chunks Guide or Python Array Shuffle: Easy Randomize Guide.

Happy coding!