Array Rotation Techniques in DSA C# - Time & Space Complexity

Time Complexity: Array Rotation Techniques

O(n)

Understanding Time Complexity

We want to understand how the time needed to rotate an array changes as the array gets bigger.

How does the number of steps grow when we rotate more elements?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public static void RotateArray(int[] arr, int k) {
    int n = arr.Length;
    k = k % n;
    int[] temp = new int[k];
    for (int i = 0; i < k; i++) {
        temp[i] = arr[n - k + i];
    }
    for (int i = n - 1; i >= k; i--) {
        arr[i] = arr[i - k];
    }
    for (int i = 0; i < k; i++) {
        arr[i] = temp[i];
    }
}
    

This code rotates an array to the right by k steps using a temporary array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Three loops each copying parts of the array.
• How many times: First loop runs k times, second loop runs n-k times, third loop runs k times.

How Execution Grows With Input

As the array size n grows, the total steps are about n (k plus n-k equals n).

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The steps grow roughly in a straight line with the size of the array.

Final Time Complexity

Time Complexity: O(n)

This means the time to rotate grows directly with the number of elements in the array.

Common Mistake

[X] Wrong: "Rotating by k steps takes only O(k) time because we only move k elements."

[OK] Correct: Because shifting the other elements also takes time, the total work depends on the whole array size, not just k.

Interview Connect

Understanding how array rotation works and its time cost helps you explain and write efficient code in interviews.

Self-Check

"What if we used the reversal algorithm for rotation instead? How would the time complexity change?"

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