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.