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 taken to rotate an array changes as the array size grows.

How does the number of steps needed to rotate an array grow when the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void rotateArray(int arr[], int n, int d) {
    int temp[d];
    for (int i = 0; i < d; i++) {
        temp[i] = arr[i];
    }
    for (int i = d; i < n; i++) {
        arr[i - d] = arr[i];
    }
    for (int i = 0; i < d; i++) {
        arr[n - d + i] = temp[i];
    }
}
    

This code rotates an array to the left by d positions using a temporary array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Three separate loops copying elements.
• How many times: First loop runs d times, second runs (n - d) times, third runs d times.

How Execution Grows With Input

As the array size n grows, the total steps grow roughly in a straight line with n.

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

Pattern observation: The work grows directly with the size of the array.

Final Time Complexity

Time Complexity: O(n)

This means the time to rotate grows in a straight line as the array gets bigger.

Common Mistake

[X] Wrong: "Rotating an array always takes the same time no matter the size."

[OK] Correct: Actually, the bigger the array, the more elements you must move, so it takes more steps.

Interview Connect

Understanding how array rotation scales helps you explain your code clearly and choose the best method during 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. Moves the last element to the front, resulting in [5, 1, 2, 3, 4]

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

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

D. Leaves the array unchanged

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 rotation to the 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 B

4. Quick Check:

   Left rotate by 1 shifts left, first element goes last [OK]

Hint: Left rotate by 1 moves first 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 is the correct C syntax to rotate an array arr of size n to the right by 1 position using a temporary variable temp?

easy

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

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

C. temp = arr[n]; for (int i = n; i > 0; i--) arr[i] = arr[i-1]; arr[0] = temp;

D. temp = arr[1]; for (int i = 1; i < n; i++) arr[i] = arr[i-1]; arr[0] = temp;

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 syntax correctness

   temp = arr[n-1]; for (int i = n-1; i > 0; i--) arr[i] = arr[i-1]; arr[0] = temp; saves last element arr[n-1], shifts elements from right to left, then sets arr[0] = temp. This matches right rotation logic.

3. Final Answer:

   temp = arr[n-1]; for (int i = n-1; i > 0; i--) arr[i] = arr[i-1]; arr[0] = temp; -> Option A

4. Quick Check:

   Right rotate saves last, shifts right, places last at front [OK]

Hint: Right rotate saves last element, shifts right, places last front [OK]

Common Mistakes:

• Using wrong index for temp (like arr[n])
• Loop direction incorrect (should go backward for right rotate)
• Shifting elements in wrong direction

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

int arr[] = {10, 20, 30, 40, 50};
int n = 5, d = 2;
for (int i = 0; i < d; i++) {
    int temp = arr[0];
    for (int j = 0; j < n-1; j++) {
        arr[j] = arr[j+1];
    }
    arr[n-1] = temp;
}
for (int i = 0; i < n; i++) printf("%d ", arr[i]);

medium

A. 30 40 50 10 20

B. 40 50 10 20 30

C. 20 30 40 50 10

D. 50 10 20 30 40

Solution

1. Step 1: Understand the code logic

   The code performs left rotation by 1, two times (d=2). Each rotation moves first element to end.

2. Step 2: Trace rotations step-by-step

   Initial: [10, 20, 30, 40, 50]
   After 1st rotation: [20, 30, 40, 50, 10]
   After 2nd rotation: [30, 40, 50, 10, 20]

3. Final Answer:

   30 40 50 10 20 -> Option A

4. Quick Check:

   Left rotate twice shifts first two elements to end [OK]

Hint: Left rotate by d moves first d elements to end [OK]

Common Mistakes:

• Confusing left and right rotation
• Rotating only once instead of d times
• Off-by-one errors in loops

4. The following code is intended to rotate an array arr of size n to the left by 1 position. What is the error?

int temp = arr[0];
for (int i = 1; i < n; i++) {
    arr[i-1] = arr[i];
}
arr[n] = temp;

medium

A. No error, code works correctly

B. Loop should start from i = 0 instead of 1

C. temp should be assigned arr[n-1] instead of arr[0]

D. Accessing arr[n] causes out-of-bounds error

Solution

1. Step 1: Analyze array indexing

   Array indices go from 0 to n-1. Accessing arr[n] is outside valid range.

2. Step 2: Identify error in assignment

   Assigning arr[n] = temp causes out-of-bounds write, which is invalid and unsafe.

3. Final Answer:

   Accessing arr[n] causes out-of-bounds error -> Option D

4. Quick Check:

   Array index must be less than n [OK]

Hint: Array indices go 0 to n-1; arr[n] is invalid [OK]

Common Mistakes:

• Using arr[n] instead of arr[n-1]
• Starting loop at wrong index
• Confusing left and right rotation logic

5. Given an array arr = [1, 2, 3, 4, 5, 6] and a rotation count d = 8, what will be the array after left rotating by d positions?

hard

A. [1, 2, 3, 4, 5, 6]

B. [5, 6, 1, 2, 3, 4]

C. [3, 4, 5, 6, 1, 2]

D. [4, 5, 6, 1, 2, 3]

Solution

1. Step 1: Calculate effective rotation

   Since rotating by d = 8 on array size n = 6, effective rotation = d % n = 8 % 6 = 2.

2. Step 2: Rotate array left by 2 positions

   Left rotating [1, 2, 3, 4, 5, 6] by 2 gives [3, 4, 5, 6, 1, 2].

3. Final Answer:

   [3, 4, 5, 6, 1, 2] -> Option C

4. Quick Check:

   Rotation count modulo array size gives effective rotation [OK]

Hint: Use d % n to find effective rotation count [OK]

Common Mistakes:

• Rotating by d without modulo causes wrong result
• Confusing left and right rotation
• Assuming array unchanged if d > n