Array Rotation Techniques in DSA Java

Mental Model

Array rotation moves elements so the array looks shifted left or right by some steps. The order stays the same but starts from a new point.

Analogy: Imagine a circular conveyor belt with boxes. Rotating the array is like moving the belt so the boxes shift positions but keep their order.

Original array:
[1] -> [2] -> [3] -> [4] -> [5] -> null
Rotate left by 2 steps:
[3] -> [4] -> [5] -> [1] -> [2] -> null

Dry Run Walkthrough

Input: array: [1, 2, 3, 4, 5], rotate left by 2

Goal: Shift the array elements left by 2 positions so the first two elements move to the end

Step 1: Reverse the first 2 elements

[2, 1, 3, 4, 5]

Why: Reversing the first part prepares for rotation by isolating the segment to move

Step 2: Reverse the remaining elements from index 2 to end

[2, 1, 5, 4, 3]

Why: Reversing the second part isolates the rest of the array for rotation

Step 3: Reverse the whole array

[3, 4, 5, 1, 2]

Why: Reversing the entire array completes the rotation by putting elements in correct order

Result:

[3, 4, 5, 1, 2]

Annotated Code

DSA Java

public class ArrayRotation {
    // Helper method to reverse elements between start and end indices
    public static void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }

    // Rotate array left by d steps using reversal algorithm
    public static void rotateLeft(int[] arr, int d) {
        int n = arr.length;
        d = d % n; // handle rotation greater than array length
        if (d == 0) return; // no rotation needed

        reverse(arr, 0, d - 1); // reverse first d elements
        reverse(arr, d, n - 1); // reverse remaining elements
        reverse(arr, 0, n - 1); // reverse whole array
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int d = 2;
        rotateLeft(arr, d);
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

d = d % n; // handle rotation greater than array length

adjust rotation steps to array size to avoid extra rotations

if (d == 0) return; // no rotation needed

skip rotation if steps is zero or multiple of array length

reverse(arr, 0, d - 1); // reverse first d elements

reverse the segment to be rotated out

reverse(arr, d, n - 1); // reverse remaining elements

reverse the rest of the array

reverse(arr, 0, n - 1); // reverse whole array

reverse entire array to complete rotation

Output

3 4 5 1 2 

Complexity Analysis

Time: O(n) because each element is reversed at most twice during the three reversals

Space: O(1) because rotation is done in place without extra arrays

vs Alternative: Naive rotation shifts elements one by one in O(n*d) time, which is slower for large d; reversal method is more efficient

Edge Cases

rotation steps d is zero

array remains unchanged

DSA Java

if (d == 0) return; // no rotation needed

rotation steps d equals array length

array remains unchanged because full rotation returns to original

DSA Java

d = d % n; // handle rotation greater than array length

rotation steps d greater than array length

rotation steps reduced modulo array length to avoid extra rotations

DSA Java

d = d % n; // handle rotation greater than array length

When to Use This Pattern

When you need to rotate an array efficiently without extra space, use the reversal algorithm pattern because it rotates in O(n) time with O(1) space.

Common Mistakes

Mistake: Rotating by shifting elements one by one inside a loop causing O(n*d) time
Fix: Use the reversal algorithm to rotate in O(n) time by reversing parts of the array

Mistake: Not handling rotation steps greater than array length
Fix: Use modulo operation to reduce rotation steps within array size

Mistake: Forgetting to reverse the entire array at the end
Fix: Complete rotation by reversing the whole array after reversing parts

Summary

Rotates an array left or right by shifting elements efficiently using the reversal method.

Use when you want to rotate arrays quickly without extra memory and avoid slow element-by-element shifts.

The key insight is that reversing parts of the array and then the whole array achieves rotation in linear time.

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