Array Rotation Techniques in DSA C - Execution Trace

Concept Flow - Array Rotation Techniques

Start with array

↓

Choose rotation direction

↓

Rotate Left

↓

Shift elements accordingly

↓

Handle wrap-around

↓

Update array state

↓

Done

Shows the flow of rotating an array either left or right by shifting elements and wrapping around.

Execution Sample

DSA C

int arr[] = {1, 2, 3, 4, 5};
int n = 5;
int d = 2; // rotate left by 2
// Rotate left by d positions
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;
}

Rotates the array left by 2 positions by shifting elements one by one.

Execution Table

Step	Operation	Array State	Pointer Changes	Visual State
1	Start	[1, 2, 3, 4, 5]	temp = arr[0] = 1	1 -> 2 -> 3 -> 4 -> 5
2	Shift elements left by 1	[2, 3, 4, 5, 5]	j moves from 0 to 3	2 -> 3 -> 4 -> 5 -> 5
3	Place temp at end	[2, 3, 4, 5, 1]	arr[n-1] = temp	2 -> 3 -> 4 -> 5 -> 1
4	Start second rotation	Current array: [2, 3, 4, 5, 1]	temp = arr[0] = 2	2 -> 3 -> 4 -> 5 -> 1
5	Shift elements left by 1	[3, 4, 5, 1, 1]	j moves from 0 to 3	3 -> 4 -> 5 -> 1 -> 1
6	Place temp at end	[3, 4, 5, 1, 2]	arr[n-1] = temp	3 -> 4 -> 5 -> 1 -> 2
7	Rotation complete	[3, 4, 5, 1, 2]	No pointer changes	3 -> 4 -> 5 -> 1 -> 2

💡 Completed 2 left rotations as d=2

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
arr	[1, 2, 3, 4, 5]	[1, 2, 3, 4, 5]	[2, 3, 4, 5, 5]	[2, 3, 4, 5, 1]	[2, 3, 4, 5, 1]	[3, 4, 5, 1, 1]	[3, 4, 5, 1, 2]	[3, 4, 5, 1, 2]
temp	undefined	1	1	1	2	2	2	2
j	undefined	0 to 3	0 to 3	undefined	0 to 3	0 to 3	undefined	undefined
i	0	0	0	0	1	1	1	2

Key Moments - 3 Insights

Why do we save arr[0] in temp before shifting?

Because shifting elements left overwrites arr[0], we save it in temp to place it at the end later. See execution_table steps 1 and 3.

Why does the inner loop run till n-1 and not n?

Because we shift elements from arr[j+1] to arr[j], j must stop at n-2 to avoid out-of-bound access. See execution_table steps 2 and 5.

What happens if d is equal to n?

Rotating by n positions results in the same array, so after d rotations, the array returns to original. This is why d is usually taken modulo n.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the array state?

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

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

C [2, 3, 4, 5, 5]

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

💡 Hint

Check the 'Array State' column at step 3 in execution_table.

At which step does the second rotation start?

A Step 5

B Step 2

C Step 4

D Step 6

💡 Hint

Look for 'Start second rotation' in the 'Operation' column.

If we change d to 3, how many times will the outer loop run?

A 3 times

B 2 times

C 5 times

D 1 time

💡 Hint

d controls the number of rotations, see variable 'i' in variable_tracker.

Concept Snapshot

Array Rotation Techniques:
- Rotate array left or right by shifting elements.
- Save first/last element before shifting to handle wrap-around.
- Repeat shifting d times for d rotations.
- Use modulo n for d to avoid full cycle rotations.
- Time complexity: O(n*d) for naive method.

Full Transcript

This visualization shows how to rotate an array left by d positions using a simple shifting method. We start with the original array and save the first element in a temporary variable. Then we shift all elements one position to the left, overwriting the first element. After shifting, we place the saved element at the end of the array. This process repeats d times. The execution table tracks each step, showing the array state and pointer changes. Key moments clarify why we save the first element and why the inner loop runs till n-1. The visual quiz tests understanding of array states at different steps and the effect of changing d. The concept snapshot summarizes the rotation technique and its complexity.

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