Array Rotation Techniques in DSA Java - Execution Trace

Concept Flow - Array Rotation Techniques

Start with array

↓

Choose rotation direction

↓

Left Rotate

↓

Shift elements accordingly

↓

Handle wrap-around

↓

Result: rotated array

The array rotation process starts with the original array, chooses left or right rotation, shifts elements, handles wrap-around, and ends with the rotated array.

Execution Sample

DSA Java

int[] arr = {1, 2, 3, 4, 5};
int d = 2; // rotate left by 2
int n = arr.length;
int[] rotated = new int[n];
for (int i = 0; i < n; i++) {
  rotated[i] = arr[(i + d) % n];
}

This code rotates the array left by 2 positions using a new array and modular arithmetic.

Execution Table

Step	Operation	Index i	Calculation (i + d) % n	rotated[i]	Rotated Array State
1	Initialize rotation	-	-	-	[_, _, _, _, _]
2	i=0: Calculate new index	0	(0+2)%5=2	arr[2]=3	[3, _, _, _, _]
3	i=1: Calculate new index	1	(1+2)%5=3	arr[3]=4	[3, 4, _, _, _]
4	i=2: Calculate new index	2	(2+2)%5=4	arr[4]=5	[3, 4, 5, _, _]
5	i=3: Calculate new index	3	(3+2)%5=0	arr[0]=1	[3, 4, 5, 1, _]
6	i=4: Calculate new index	4	(4+2)%5=1	arr[1]=2	[3, 4, 5, 1, 2]
7	Rotation complete	-	-	-	[3, 4, 5, 1, 2]

💡 All elements processed, rotated array fully populated.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
i	-	0	1	2	3	4	-
rotated	[_, _, _, _, _]	[3, _, _, _, _]	[3, 4, _, _, _]	[3, 4, 5, _, _]	[3, 4, 5, 1, _]	[3, 4, 5, 1, 2]	[3, 4, 5, 1, 2]

Key Moments - 3 Insights

Why do we use (i + d) % n instead of just i + d?

Because (i + d) % n wraps the index around the array length, ensuring we don't go out of bounds. See execution_table rows 2-6 where indices wrap from 4 back to 0.

What happens if d is equal to the array length?

If d equals n, (i + d) % n equals i, so the array stays the same. This is why rotation by the array length results in the original array, as shown by the modular arithmetic in the calculation column.

Why do we need a new array for rotation?

Using a new array avoids overwriting elements before they are read. This is shown in the variable_tracker where rotated array builds step-by-step without losing original values.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the value of rotated[2]?

A 3

B 4

C 5

D 1

💡 Hint

Check the 'rotated[i]' column at Step 4 where i=2.

At which step does the calculation wrap the index back to 0?

A Step 5

B Step 3

C Step 6

D Step 7

💡 Hint

Look at the 'Calculation (i + d) % n' column for value 0.

If d was 5 (array length), how would the rotated array look after completion?

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

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

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

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

💡 Hint

Recall modular arithmetic with d equal to array length from key_moments.

Concept Snapshot

Array Rotation Techniques:
- Rotate array left or right by d positions.
- Use modular arithmetic: new_index = (i + d) % n for left rotation.
- Use a new array to avoid overwriting.
- Rotation by array length returns original array.
- Wrap-around ensures indices stay within bounds.

Full Transcript

This visualization shows how to rotate an array by shifting elements using modular arithmetic. We start with the original array and choose the rotation direction. For left rotation by d positions, each element at index i moves to (i + d) modulo n. We use a new array to store rotated elements to avoid overwriting. The execution table traces each step, showing how indices wrap around the array length. Key moments clarify why modular arithmetic is essential and why rotation by the array length results in the same array. The visual quiz tests understanding of index calculations and rotation effects.

Practice

1. What does rotating an array to the left by 1 position mean?
Example: [1, 2, 3, 4] rotated left by 1 becomes?

easy

A. [2, 3, 4, 1]

B. [4, 1, 2, 3]

C. [1, 4, 3, 2]

D. [3, 4, 1, 2]

Solution

1. Step 1: Understand left rotation

   Left rotation by 1 means each element moves one step to the left, and the first element moves to the end.

2. Step 2: Apply left rotation on example

   For [1, 2, 3, 4], after left rotation by 1, it becomes [2, 3, 4, 1].

3. Final Answer:

   [2, 3, 4, 1] -> Option A

4. Quick Check:

   Left rotate by 1 moves first element to end [OK]

Hint: Left rotate shifts elements left, first goes to last [OK]

Common Mistakes:

• Confusing left rotation with right rotation
• Not moving the first element to the end
• Shifting elements in the wrong direction

2. Which of the following Java code snippets correctly rotates an array arr of length n to the right by 1 position?

easy

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

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

C. for(int i = 0; i < n; i++) arr[i] = arr[(i+1) % n];

D. int temp = arr[0]; arr[0] = arr[n-1]; arr[n-1] = temp;

Solution

1. Step 1: Understand right rotation by 1

   Right rotation by 1 moves each element one step right, last element moves to first position.

2. Step 2: Check code correctness

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

3. Final Answer:

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

4. Quick Check:

   Right rotate shifts right, last to first [OK]

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

Common Mistakes:

• Using left rotation logic for right rotation
• Incorrect loop direction causing overwrite
• Swapping only first and last elements

3. What is the output of the following Java code?

int[] arr = {10, 20, 30, 40, 50};
int d = 2;
for(int i = 0; i < d; i++) {
    int temp = arr[0];
    for(int j = 0; j < arr.length - 1; j++) {
        arr[j] = arr[j+1];
    }
    arr[arr.length - 1] = temp;
}
System.out.println(java.util.Arrays.toString(arr));

medium

A. [20, 30, 40, 50, 10]

B. [30, 40, 50, 10, 20]

C. [50, 10, 20, 30, 40]

D. [10, 20, 30, 40, 50]

Solution

1. Step 1: Understand the loop rotates array left by 1, repeated d times

   Each iteration moves first element to end, shifting left by 1. Loop runs twice (d=2).

2. Step 2: Trace array after each rotation

   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 B

4. Quick Check:

   Left rotate by 2 shifts first 2 elements to end [OK]

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

Common Mistakes:

• Confusing left and right rotation
• Not repeating rotation d times
• Off-by-one errors in loops

4. Identify the error in this Java code that attempts to rotate an array arr of length n to the left by 1:

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

medium

A. temp should be assigned after the loop

B. Array length n is incorrect

C. Loop runs out of bounds accessing arr[n]

D. No error, code is correct

Solution

1. Step 1: Analyze the loop range and array access

   The loop runs from i=0 to i=n-1, but inside it accesses arr[i+1]. For i=n-1, arr[i+1] = arr[n], which is out of bounds.

2. Step 2: Identify the cause of error

   Accessing arr[n] causes ArrayIndexOutOfBoundsException. The loop should run only till i < n-1.

3. Final Answer:

   Loop runs out of bounds accessing arr[n] -> Option C

4. Quick Check:

   Array index must be within 0 to n-1 [OK]

Hint: Check array indices carefully to avoid out-of-bounds [OK]

Common Mistakes:

• Looping till i < n instead of i < n-1
• Ignoring array length limits
• Misplacing temp assignment

5. Given an array arr = [5, 10, 15, 20, 25, 30], how can you rotate it to the right by 3 positions efficiently without using extra space?

hard

A. Swap elements pairwise from start to end 3 times

B. Shift elements one by one to the right 3 times using nested loops

C. Copy last 3 elements to a temp array, shift rest right, then copy temp to front

D. Reverse entire array, reverse first 3 elements, then reverse remaining elements

Solution

1. Step 1: Understand the reversal algorithm for rotation

   To rotate right by d, reverse whole array, then reverse first d elements, then reverse remaining n-d elements.

2. Step 2: Apply to example

   Array: [5,10,15,20,25,30]
   Reverse all: [30,25,20,15,10,5]
   Reverse first 3: [20,25,30,15,10,5]
   Reverse last 3: [20,25,30,5,10,15]

3. Final Answer:

   Reverse entire array, reverse first 3 elements, then reverse remaining elements -> Option D

4. Quick Check:

   Reversal method rotates array efficiently without extra space [OK]

Hint: Use reversal method: reverse all, then parts [OK]

Common Mistakes:

• Using extra space instead of in-place reversal
• Shifting elements one by one inefficiently
• Incorrect order of reversals