Array Rotation Techniques in DSA Python

Mental Model

Array rotation means moving elements so the array looks shifted left or right by some steps. We imagine the array as a circle where elements wrap around.

Analogy: Think of a carousel with horses arranged in a circle. Rotating the carousel moves each horse forward or backward, but the order stays the same, just shifted.

Initial array:
[1] -> [2] -> [3] -> [4] -> [5] -> null
Rotate by 2 steps to the left means:
[3] -> [4] -> [5] -> [1] -> [2] -> null

Dry Run Walkthrough

Input: array: [1, 2, 3, 4, 5], rotate left by 2 steps

Goal: Shift the array elements left by 2 positions so the first two elements move to the end

Step 1: Reverse the first 2 elements

[2, 1, 3, 4, 5]

Why: Reversing the first part prepares for rotation by breaking the array into parts

Step 2: Reverse the remaining elements from index 2 to end

[2, 1, 5, 4, 3]

Why: Reversing the second part isolates the elements that will move to the front

Step 3: Reverse the whole array

[3, 4, 5, 1, 2]

Why: Reversing the entire array completes the rotation by putting elements in correct order

Result:

[3, 4, 5, 1, 2]

Annotated Code

DSA Python

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

def rotate_left(arr, k):
    n = len(arr)
    k %= n  # handle rotation greater than length
    reverse(arr, 0, k - 1)  # reverse first k elements
    reverse(arr, k, n - 1)  # reverse rest
    reverse(arr, 0, n - 1)  # reverse whole array

arr = [1, 2, 3, 4, 5]
rotate_left(arr, 2)
print(arr)

k %= n # handle rotation greater than length

adjust rotation steps to within array length

reverse(arr, 0, k - 1) # reverse first k elements

reverse the first part to prepare for rotation

reverse(arr, k, n - 1) # reverse rest

reverse the remaining part to isolate elements

reverse(arr, 0, n - 1) # reverse whole array

reverse entire array to complete rotation

Output

[3, 4, 5, 1, 2]

Complexity Analysis

Time: O(n) because each element is reversed at most twice during the three reversals

Space: O(1) because rotation is done in place without extra arrays

vs Alternative: Naive approach shifts elements one by one in O(n*k) time, which is slower for large k; reversal method is efficient and uses constant space

Edge Cases

rotation steps k is 0

array remains unchanged

DSA Python

k %= n  # handle rotation greater than length

rotation steps k equal to array length

array remains unchanged because full rotation returns to original

DSA Python

k %= n  # handle rotation greater than length

empty array

no operation, array stays empty

DSA Python

n = len(arr)

When to Use This Pattern

When you need to shift array elements efficiently without extra space, use the reversal technique because it rotates in linear time with constant space.

Common Mistakes

Mistake: Rotating by k without taking modulo with array length causes index errors or incorrect results
Fix: Always use k %= n to adjust rotation steps within array length

Mistake: Trying to rotate by moving elements one by one leads to slow O(n*k) time
Fix: Use the reversal method to achieve O(n) time

Summary

Rotates array elements left or right by k steps efficiently using reversals.

Use when you want to shift array elements without extra space and in linear time.

The key insight is that reversing parts of the array and then the whole array achieves rotation.

Practice

1. What does rotating an array to the left by 1 position do to the elements?

easy

A. Moves each element one step to the right, last element goes to the front

B. Moves each element one step to the left, first element goes to the end

C. Reverses the array

D. Sorts the array in ascending order

Solution

1. Step 1: Understand left rotation

   Left rotation by 1 means the element at index 0 moves to the end, and all others shift left by one.

2. Step 2: Visualize the movement

   For example, [1, 2, 3] becomes [2, 3, 1] after left rotation by 1.

3. Final Answer:

   Moves each element one step to the left, first element goes to the end -> Option B

4. Quick Check:

   Left rotation = shift left + wrap first element [OK]

Hint: Left rotation shifts left, first element moves to end [OK]

Common Mistakes:

• Confusing left rotation with right rotation
• Thinking rotation sorts the array
• Assuming rotation reverses the array

2. Which of the following is the correct Python syntax to rotate an array arr to the right by 2 positions using slicing?

easy

A. arr = arr[-2:] + arr[:-2]

B. arr = arr[2:] + arr[:2]

C. arr = arr[:2] + arr[2:]

D. arr = arr[-2:] - arr[:-2]

Solution

1. Step 1: Understand right rotation with slicing

   Right rotation by 2 means last 2 elements move to front, rest shift right.

2. Step 2: Apply slicing syntax

   arr[-2:] gets last 2 elements, arr[:-2] gets all except last 2. Concatenating gives rotated array.

3. Final Answer:

   arr = arr[-2:] + arr[:-2] -> Option A

4. Quick Check:

   Right rotation by 2 = last 2 + rest [OK]

Hint: Right rotation by k = last k elements + rest [OK]

Common Mistakes:

• Using + operator incorrectly with slices
• Confusing left and right rotation slices
• Using subtraction operator instead of concatenation

3. What is the output of the following code?

arr = [10, 20, 30, 40, 50]
k = 3
rotated = arr[k:] + arr[:k]
print(rotated)

medium

A. [50, 10, 20, 30, 40]

B. [30, 40, 50, 10, 20]

C. [20, 30, 40, 50, 10]

D. [40, 50, 10, 20, 30]

Solution

1. Step 1: Identify rotation type

   arr[k:] + arr[:k] rotates array left by k=3 positions.

2. Step 2: Perform slicing and concatenation

   arr[3:] = [40, 50], arr[:3] = [10, 20, 30], combined = [40, 50, 10, 20, 30]

3. Final Answer:

   [40, 50, 10, 20, 30] -> Option D

4. Quick Check:

   Left rotation by 3 = [40,50] + [10,20,30] [OK]

Hint: arr[k:] + arr[:k] = left rotate by k [OK]

Common Mistakes:

• Mixing left and right rotation logic
• Incorrect slicing indices
• Misreading k value

4. The following code is intended to rotate an array arr to the right by k positions. What is the error?

def rotate_right(arr, k):
    n = len(arr)
    k = k % n
    rotated = arr[k:] + arr[:k]
    return rotated

print(rotate_right([1,2,3,4,5], 2))

medium

A. The slicing indices perform left rotation, not right rotation

B. The modulo operation is incorrect

C. The function does not return anything

D. The print statement is missing parentheses

Solution

1. Step 1: Analyze slicing for rotation

   arr[k:] + arr[:k] rotates array left by k, not right.

2. Step 2: Correct right rotation slicing

   Right rotation by k should be arr[-k:] + arr[:-k].

3. Final Answer:

   The slicing indices perform left rotation, not right rotation -> Option A

4. Quick Check:

   Right rotation needs arr[-k:] + arr[:-k] [OK]

Hint: Right rotation uses negative slicing indices [OK]

Common Mistakes:

• Using left rotation slices for right rotation
• Ignoring modulo to handle k > n
• Forgetting to return the rotated array

5. Given an array arr = [3, 8, 9, 7, 6], how would you rotate it to the right by k = 3 positions using a single Python statement without slicing?

hard

A. Use arr.sort() then reverse

B. Use arr.reverse() three times

C. Use a loop to pop last element and insert at front 3 times

D. Use arr.append(arr.pop()) once

Solution

1. Step 1: Understand rotation without slicing

   Rotating right by 3 means moving last element to front 3 times.

2. Step 2: Use loop with pop and insert

   Loop 3 times: pop last element and insert at index 0 to rotate right.

3. Final Answer:

   Use a loop to pop last element and insert at front 3 times -> Option C

4. Quick Check:

   Pop + insert at front repeated k times = right rotation [OK]

Hint: Pop last and insert front k times for right rotation [OK]

Common Mistakes:

• Using reverse instead of rotation
• Sorting array mistakenly
• Only popping once instead of k times