Array Rotation Techniques in DSA C++

Mental Model

Rotating an array means moving its elements so that some elements shift to the front or back, like turning a circle.

Analogy: Imagine a circular conveyor belt with boxes. Rotating the belt moves boxes forward or backward, but the order stays the same relative to the belt.

Array: [1] -> [2] -> [3] -> [4] -> [5] -> null
Rotation pointer ↑ at index 0 before rotation

Dry Run Walkthrough

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

Goal: Move last 2 elements to the front, shifting others right

Step 1: Reverse entire array

[5] -> [4] -> [3] -> [2] -> [1] -> null

Why: Reversing whole array prepares for splitting rotation parts

Step 2: Reverse first 2 elements

[4] -> [5] -> [3] -> [2] -> [1] -> null

Why: Reversing first part restores order of rotated elements

Step 3: Reverse remaining 3 elements

[4] -> [5] -> [1] -> [2] -> [3] -> null

Why: Reversing second part restores order of remaining elements

Result:

Final rotated array: [4] -> [5] -> [1] -> [2] -> [3] -> null

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void reverse(vector<int>& arr, int start, int end) {
    while (start < end) {
        swap(arr[start], arr[end]); // swap elements at start and end
        start++; // move start forward
        end--; // move end backward
    }
}

void rotateRight(vector<int>& arr, int k) {
    int n = arr.size();
    k = k % n; // handle rotations larger than array size
    if (k == 0) return; // no rotation needed
    reverse(arr, 0, n - 1); // reverse whole array
    reverse(arr, 0, k - 1); // reverse first k elements
    reverse(arr, k, n - 1); // reverse remaining elements
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    int k = 2;
    rotateRight(arr, k);
    for (int num : arr) {
        cout << num << " -> ";
    }
    cout << "null" << endl;
    return 0;
}

k = k % n; // handle rotations larger than array size

reduce rotation steps to within array length

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

skip rotation if k is zero after modulo

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

reverse entire array to prepare for rotation

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

reverse first part to restore rotated elements order

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

reverse second part to restore remaining elements order

Output

4 -> 5 -> 1 -> 2 -> 3 -> null

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 O(n*k), this method is faster for large k

Edge Cases

k is zero or multiple of array length

No rotation occurs, array stays the same

DSA C++

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

array has only one element

Rotation does nothing, array unchanged

DSA C++

k = k % n; // handle rotations larger than array size

k larger than array length

Rotation steps reduced by modulo to valid range

DSA C++

k = k % n; // handle rotations larger than array size

When to Use This Pattern

When asked to rotate an array efficiently, use the reverse method to achieve rotation in O(n) time without extra space.

Common Mistakes

Mistake: Rotating by shifting elements one by one leading to O(n*k) time
Fix: Use the three-step reverse method to rotate in O(n) time

Mistake: Not handling k greater than array length causing index errors
Fix: Use k = k % n to reduce rotation steps within array size

Summary

Rotates an array by moving elements to the right or left by k positions.

Use when you need to shift array elements efficiently without extra space.

The key insight is reversing parts of the array to achieve rotation in three steps.

Practice

1. What does rotating an array to the left by 1 position do to the elements?

easy

A. Moves the last element to the front and shifts all others one position right

B. Moves the first element to the end and shifts all others one position left

C. Reverses the entire array

D. Sorts the array in ascending order

Solution

1. Step 1: Understand left rotation by 1

   Left rotation by 1 means the element at index 0 moves to the end.

2. Step 2: Effect on other elements

   All other elements shift one position to the left to fill the gap.

3. Final Answer:

   Moves the first element to the end and shifts all others one position left -> Option B

4. Quick Check:

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

Hint: Left rotate by 1 moves front element to back [OK]

Common Mistakes:

• Confusing left rotation with right rotation
• Thinking rotation reverses the array
• Assuming rotation sorts the array

2. Which of the following is the correct syntax to rotate an array arr of size n to the right by 1 position in C++?

easy

A. std::rotate(arr, arr + n, arr + 1);

B. std::rotate(arr, arr + 1, arr + n);

C. std::rotate(arr, arr + n - 1, arr + n);

D. std::rotate(arr + 1, arr, arr + n);

Solution

1. Step 1: Understand std::rotate parameters

   std::rotate takes three pointers: first, middle, last. It rotates the range [first, last) so that the element at middle becomes first.

2. Step 2: Rotate right by 1 means last element moves to front

   To rotate right by 1, middle should point to the last element (arr + n - 1).

3. Final Answer:

   std::rotate(arr, arr + n - 1, arr + n); -> Option C

4. Quick Check:

   Right rotate by 1 uses middle = last-1 [OK]

Hint: Right rotate by 1 uses middle = last-1 in std::rotate [OK]

Common Mistakes:

• Using middle = first + 1 for right rotation
• Swapping parameters order incorrectly
• Confusing rotate range boundaries

3. What is the output of the following C++ code?

int arr[] = {10, 20, 30, 40, 50};
int n = 5;
int d = 2;
std::rotate(arr, arr + d, arr + n);
for(int i = 0; i < n; i++) std::cout << arr[i] << " ";

medium

A. 30 40 50 10 20

B. 40 50 10 20 30

C. 50 10 20 30 40

D. 20 30 40 50 10

Solution

1. Step 1: Understand std::rotate with d=2

   std::rotate(arr, arr + 2, arr + 5) moves elements starting from index 2 to front.

2. Step 2: Rearrange array after rotation

   Elements from index 2 to 4: 30, 40, 50 come first, then elements from index 0 to 1: 10, 20.

3. Final Answer:

   30 40 50 10 20 -> Option A

4. Quick Check:

   Rotate left by 2 shifts first 2 elements to end [OK]

Hint: Rotate left by d moves first d elements to end [OK]

Common Mistakes:

• Confusing left and right rotation
• Off-by-one errors in index calculation
• Printing array before rotation

4. The following code is intended to rotate an array arr of size n to the left by d positions. What is the error?

void rotateLeft(int arr[], int n, int d) {
    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;
    }
}

medium

A. temp should be assigned arr[n-1] instead of arr[0]

B. Inner loop should run from j=1 to n-1

C. The outer loop should run from i=1 to d

D. Accessing arr[n] causes out-of-bounds error

Solution

1. Step 1: Analyze inner loop index usage

   The inner loop runs j from 0 to n-1, but accesses arr[j+1]. When j = n-1, arr[j+1] = arr[n] is accessed.

2. Step 2: Identify out-of-bounds access

   Array indices go from 0 to n-1, so arr[n] is invalid and causes out-of-bounds error.

3. Final Answer:

   Accessing arr[n] causes out-of-bounds error -> Option D

4. Quick Check:

   Array index out of bounds at arr[n] [OK]

Hint: Array indices go 0 to n-1, arr[n] is invalid [OK]

Common Mistakes:

• Ignoring out-of-bounds access
• Misunderstanding loop ranges
• Incorrectly assigning temp value

5. Given an array arr = {1, 2, 3, 4, 5, 6, 7} and d = 3, which sequence of operations correctly rotates the array to the left by d positions using the reversal algorithm?

hard

A. Reverse first d elements, reverse last n-d elements, then reverse whole array

B. Reverse whole array, reverse first d elements, then reverse last n-d elements

C. Reverse first d elements, reverse whole array, then reverse last n-d elements

D. Reverse whole array, reverse last n-d elements, then reverse first d elements

Solution

1. Step 1: Understand reversal algorithm steps

   To rotate left by d, first reverse the first d elements.

2. Step 2: Reverse last n-d elements, then reverse whole array

   Next reverse the last n-d elements, finally reverse the entire array to get the rotated result.

3. Final Answer:

   Reverse first d elements, reverse last n-d elements, then reverse whole array -> Option A

4. Quick Check:

   Reversal algorithm order = first d, last n-d, whole [OK]

Hint: Left rotate reversal: first d, last n-d, then whole [OK]

Common Mistakes:

• Reversing parts before whole array
• Mixing order of reversing segments
• Confusing left and right rotation steps