Array Rotation Techniques in DSA C#

Mental Model

Array rotation moves elements so that the array looks shifted left or right by some steps. The order stays the same but starts from a new point.

Analogy: Imagine a circular conveyor belt with boxes. Rotating the array is like moving the belt so the boxes shift positions but keep their order.

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

Dry Run Walkthrough

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

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 flipping the segment to be moved

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

[2, 1, 5, 4, 3]

Why: Reversing the rest prepares the second part for final rotation

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 C#

using System;

class ArrayRotation {
    // Helper to reverse part of array from start to end indices
    static void Reverse(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }

    // Rotate array left by d positions using reversal algorithm
    static void RotateLeft(int[] arr, int d) {
        int n = arr.Length;
        if (n == 0) return;
        d = d % n; // handle rotations larger than array size
        if (d == 0) return; // no rotation needed

        Reverse(arr, 0, d - 1); // reverse first d elements
        Reverse(arr, d, n - 1); // reverse rest
        Reverse(arr, 0, n - 1); // reverse whole array
    }

    static void PrintArray(int[] arr) {
        for (int i = 0; i < arr.Length; i++) {
            Console.Write(arr[i]);
            if (i != arr.Length - 1) Console.Write(" -> ");
        }
        Console.WriteLine(" -> null");
    }

    static void Main() {
        int[] arr = {1, 2, 3, 4, 5};
        int d = 2;
        Console.WriteLine("Original array:");
        PrintArray(arr);

        RotateLeft(arr, d);

        Console.WriteLine($"Array after rotating left by {d}:");
        PrintArray(arr);
    }
}

d = d % n; // handle rotations larger than array size

reduce rotation steps to within array length to avoid unnecessary full rotations

if (d == 0) return; // no rotation needed

skip rotation if steps is zero after modulo

Reverse(arr, 0, d - 1); // reverse first d elements

reverse the segment to be rotated from the front

Reverse(arr, d, n - 1); // reverse rest

reverse the remaining segment after the first d elements

Reverse(arr, 0, n - 1); // reverse whole array

reverse entire array to complete rotation

Output

Original array:

1 -> 2 -> 3 -> 4 -> 5 -> null

Array after rotating left by 2:

3 -> 4 -> 5 -> 1 -> 2 -> null

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 rotation by shifting elements one by one is O(n*d), which is slower for large d; reversal method is more efficient

Edge Cases

rotation steps d is zero

array remains unchanged

DSA C#

if (d == 0) return; // no rotation needed

rotation steps d is equal to array length

array remains unchanged because full rotation returns to original

DSA C#

d = d % n; // handle rotations larger than array size

rotation steps d larger than array length

rotation steps reduced modulo array length to avoid extra rotations

DSA C#

d = d % n; // handle rotations larger than array size

empty array

no operation, safe to run

DSA C#

if (n == 0) return; // handles empty array safely

When to Use This Pattern

When you need to rotate or shift array elements efficiently without extra space, use the reversal algorithm pattern because it rotates in O(n) time with O(1) space.

Common Mistakes

Mistake: Rotating by shifting elements one by one inside a loop causing O(n*d) time
Fix: Use the reversal algorithm to rotate in O(n) time by reversing parts of the array

Mistake: Not handling rotation steps larger than array length causing incorrect results
Fix: Use modulo operation to reduce rotation steps within array length

Mistake: Forgetting to reverse the entire array at the end
Fix: Always reverse the whole array after reversing the two parts

Summary

Rotates an array left or right by shifting elements efficiently using reversals.

Use when you want to rotate arrays in place without extra space and with good performance.

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

Practice

1. What does a left rotation by 1 position do to the array [1, 2, 3, 4, 5]?

easy

A. Leaves the array unchanged

B. Moves the last element to the front, resulting in [5, 1, 2, 3, 4]

C. Reverses the array, resulting in [5, 4, 3, 2, 1]

D. Moves the first element to the end, resulting in [2, 3, 4, 5, 1]

Solution

1. Step 1: Understand left rotation by 1

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

2. Step 2: Apply to given array

   Starting with [1, 2, 3, 4, 5], after rotation it becomes [2, 3, 4, 5, 1].

3. Final Answer:

   Moves the first element to the end, resulting in [2, 3, 4, 5, 1] -> Option D

4. Quick Check:

   Left rotation by 1 shifts left, first element to end [OK]

Hint: Left rotation moves front element to end [OK]

Common Mistakes:

• Confusing left rotation with right rotation
• Thinking rotation reverses the array
• Assuming array stays the same

2. Which of the following C# code snippets correctly performs a right rotation by 1 on an integer array arr?

easy

A. int last = arr[arr.Length - 1]; for (int i = arr.Length - 1; i > 0; i--) arr[i] = arr[i - 1]; arr[0] = last;

B. int first = arr[0]; for (int i = 0; i < arr.Length - 1; i++) arr[i] = arr[i + 1]; arr[arr.Length - 1] = first;

C. Array.Reverse(arr);

D. Array.Sort(arr);

Solution

1. Step 1: Understand right rotation by 1

   Right rotation by 1 moves the last element to the front, shifting others right.

2. Step 2: Check code snippets

   int last = arr[arr.Length - 1]; for (int i = arr.Length - 1; i > 0; i--) arr[i] = arr[i - 1]; arr[0] = last; saves last element, shifts elements right, then places last at front. This matches right rotation.

3. Final Answer:

   int last = arr[arr.Length - 1]; for (int i = arr.Length - 1; i > 0; i--) arr[i] = arr[i - 1]; arr[0] = last; -> Option A

4. Quick Check:

   Right rotation moves last element to front [OK]

Hint: Right rotation moves last element to front [OK]

Common Mistakes:

• Using left rotation code for right rotation
• Reversing array instead of rotating
• Sorting array instead of rotating

3. What is the output of the following C# code?

int[] arr = {10, 20, 30, 40, 50};
int d = 2;
int n = arr.Length;
int[] rotated = new int[n];
for (int i = 0; i < n; i++) {
  rotated[i] = arr[(i + d) % n];
}
Console.WriteLine(string.Join(", ", rotated));

medium

A. 40, 50, 10, 20, 30

B. 30, 40, 50, 10, 20

C. 50, 10, 20, 30, 40

D. 10, 20, 30, 40, 50

Solution

1. Step 1: Understand rotation logic in code

   Each element at index i in rotated is assigned arr[(i + d) % n], which means left rotation by d=2.

2. Step 2: Calculate rotated array elements

   For i=0: arr[(0+2)%5]=arr[2]=30
   i=1: arr[3]=40
   i=2: arr[4]=50
   i=3: arr[0]=10
   i=4: arr[1]=20
   Rotated array = [30, 40, 50, 10, 20]

3. Final Answer:

   30, 40, 50, 10, 20 -> Option B

4. Quick Check:

   Left rotation by 2 shifts elements left by 2 [OK]

Hint: Use modulo to wrap index for rotation [OK]

Common Mistakes:

• Confusing left and right rotation
• Forgetting modulo causes index error
• Misindexing array elements

4. The following code is intended to perform a left rotation by 3 on array arr. What is the error?

int[] arr = {1, 2, 3, 4, 5};
int d = 3;
int n = arr.Length;
int[] rotated = new int[n];
for (int i = 0; i < n; i++) {
  rotated[i] = arr[(i - d) % n];
}

medium

A. Using (i - d) % n causes negative index error

B. Loop should run from d to n

C. Array size is incorrect

D. Rotation direction is right instead of left

Solution

1. Step 1: Analyze index calculation

   The code uses (i - d) % n. When i < d, (i - d) is negative, so modulo gives negative result in C#.

2. Step 2: Understand modulo behavior in C#

   C# modulo with negative numbers returns negative values, causing invalid negative indices for array access.

3. Final Answer:

   Using (i - d) % n causes negative index error -> Option A

4. Quick Check:

   Negative modulo causes invalid array index [OK]

Hint: Add n before modulo to avoid negative indices [OK]

Common Mistakes:

• Ignoring negative modulo results
• Changing loop range incorrectly
• Confusing left and right rotation

5. Given an array arr = [4, 8, 15, 16, 23, 42], how would you perform a left rotation by d = 8 positions efficiently in C#?

hard

A. Reverse the array twice

B. Rotate by d positions directly without modulo

C. Rotate by d % arr.Length positions using a temporary array

D. Sort the array after rotation

Solution

1. Step 1: Understand rotation with d > array length

   Rotating by d=8 on array length 6 is same as rotating by d % 6 = 2 positions.

2. Step 2: Use modulo and temporary array

   Use d % n to find effective rotation, then rotate using a temporary array or in-place method.

3. Final Answer:

   Rotate by d % arr.Length positions using a temporary array -> Option C

4. Quick Check:

   Rotation by d mod length avoids unnecessary full rotations [OK]

Hint: Use d % array length to reduce rotations [OK]

Common Mistakes:

• Rotating by d without modulo wastes time
• Trying to sort array after rotation
• Using reverse without correct steps