Array Rotation Techniques in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is array rotation?

Array rotation means shifting the elements of an array to the left or right by a certain number of positions, wrapping around the elements that go past the end to the other side.

intermediate

Explain the 'Rotate by Reversal' technique.

Rotate by Reversal rotates an array by reversing parts of the array: first reverse the part before the rotation point, then reverse the part after, and finally reverse the whole array to get the rotated result.

intermediate

What is the time complexity of rotating an array using the 'Rotate by Reversal' method?

The time complexity is O(n), where n is the number of elements in the array, because each element is reversed at most once in each reversal step, and there are three reversal steps.

beginner

Describe the 'Rotate by Temporary Array' method.

This method uses an extra temporary array to store the elements that will be rotated out, then shifts the remaining elements, and finally copies the stored elements back to the array's end.

intermediate

What is a common challenge when rotating arrays in-place?

A common challenge is to rotate the array without losing any elements and without using extra space, which requires careful swapping or reversing to avoid overwriting values.

What does rotating an array to the left by 2 positions do to the array [1, 2, 3, 4, 5]?

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

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

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

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

Rotating left by 2 moves the first two elements to the end, so [1, 2, 3, 4, 5] becomes [3, 4, 5, 1, 2].

Which technique uses reversing parts of the array to rotate it?

A Rotate by Reversal

B Rotate by Temporary Array

C Rotate by Swapping

D Rotate by Sorting

Rotate by Reversal involves reversing parts of the array to achieve rotation.

What is the extra space complexity of the 'Rotate by Temporary Array' method?

A O(1)

B O(d)

C O(log n)

D O(n)

It uses extra space proportional to the number of positions rotated (d), so O(d).

If you rotate an array of size 5 by 7 positions to the right, how many effective rotations happen?

A 2

B 5

C 7

D 0

Rotations wrap around the array size, so 7 % 5 = 2 effective rotations.

Which method can rotate an array in-place without extra space?

A Rotate by Sorting

B Rotate by Temporary Array

C Rotate by Copying

D Rotate by Reversal

Rotate by Reversal rotates the array in-place using only swaps and reversals.

Explain how the 'Rotate by Reversal' technique works step-by-step.

Think about reversing segments to move elements around.

Describe the difference between rotating an array using a temporary array and rotating it in-place.

Consider space usage and how elements are moved.

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