Array Rotation Techniques in DSA Rust

Mental Model

Array rotation means moving 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 a different box comes to the front, but the order of boxes stays the same.

Original array:
[1] -> [2] -> [3] -> [4] -> [5] -> null
Rotate by 2 to the left:
[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 element moves to the end twice

Step 1: reverse the whole array

[5, 4, 3, 2, 1]

Why: Reversing the whole array prepares it for partial reversals to achieve rotation

Step 2: reverse the first n-k elements (here first 3 elements)

[3, 4, 5, 2, 1]

Why: Reversing the first part restores their original order but shifted

Step 3: reverse the last k elements (here last 2 elements)

[3, 4, 5, 1, 2]

Why: Reversing the last part restores their original order but shifted

Result:

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

Annotated Code

DSA Rust

fn reverse(arr: &mut [i32], start: usize, end: usize) {
    let mut left = start;
    let mut right = end;
    while left < right {
        arr.swap(left, right); // swap elements at left and right
        left += 1; // move left pointer forward
        right -= 1; // move right pointer backward
    }
}

fn rotate_left(arr: &mut [i32], k: usize) {
    let n = arr.len();
    if n == 0 { return; } // handle empty array
    let k = k % n; // normalize k if larger than array length
    if k == 0 { return; } // no rotation needed

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

fn main() {
    let mut arr = vec![1, 2, 3, 4, 5];
    rotate_left(&mut arr, 2);
    for val in &arr {
        print!("{} -> ", val);
    }
    print!("null\n");
}

arr.swap(left, right); // swap elements at left and right

exchange elements to reverse the segment

left += 1; // move left pointer forward

advance left pointer to continue reversal

right -= 1; // move right pointer backward

move right pointer backward to continue reversal

let k = k % n; // normalize k if larger than array length

adjust rotation steps to array size

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

prepare array for rotation by reversing all elements

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

restore order of last part shifted by rotation

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

restore order of first part shifted by rotation

Output

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

Complexity Analysis

Time: O(n) because each element is swapped at most twice during reversals

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

vs Alternative: Naive approach shifts elements one by one in O(n*k) time, which is slower for large k

Edge Cases

empty array

function returns immediately without error

DSA Rust

if n == 0 { return; } // handle empty array

rotation steps k is zero

array remains unchanged

DSA Rust

if k == 0 { return; } // no rotation needed

rotation steps k equal to array length

array remains unchanged after rotation

DSA Rust

let k = k % n; // normalize k if larger than array length

When to Use This Pattern

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

Common Mistakes

Mistake: Not normalizing k with modulo leads to incorrect rotation when k > array length
Fix: Use k = k % n to handle rotation steps larger than array size

Mistake: Reversing segments in wrong order or wrong indices causes wrong final array
Fix: Follow the exact order: reverse whole array, then reverse first n-k, then reverse last k

Summary

Rotates an array left by k positions using three reversals.

Use when you want an in-place efficient array rotation.

The key insight is that reversing parts of the array rearranges elements to achieve rotation.

Practice

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

easy

A. The last two elements move to the front, resulting in [4, 5, 1, 2, 3]

B. The first two elements move to the end, resulting in [3, 4, 5, 1, 2]

C. The array is reversed, resulting in [5, 4, 3, 2, 1]

D. The array remains unchanged

Solution

1. Step 1: Understand left rotation by 2

   Left rotation by 2 means removing the first two elements and placing them at the end.

2. Step 2: Apply rotation on given array

   Starting with [1, 2, 3, 4, 5], removing first two elements [1, 2] and appending them at the end gives [3, 4, 5, 1, 2].

3. Final Answer:

   [3, 4, 5, 1, 2] -> Option B

4. Quick Check:

   Left rotate by 2 = first 2 elements moved to end [OK]

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

Common Mistakes:

• Confusing left rotation with right rotation
• Not moving elements but just swapping
• Thinking rotation reverses the array

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

easy

A. let rotated = [&arr[0..4], &arr[4..5]].concat();

B. let rotated = [&arr[1..5], &arr[0..1]].concat();

C. let rotated = [&arr[4..5], &arr[0..4]].concat();

D. let rotated = [&arr[3..5], &arr[0..3]].concat();

Solution

1. Step 1: Understand right rotation by 1

   Right rotation by 1 means last element moves to front, rest shift right.

2. Step 2: Check code slices for correct order

   let rotated = [&arr[4..5], &arr[0..4]].concat(); takes last element arr[4..5] and then first 4 elements arr[0..4], concatenating them correctly.

3. Final Answer:

   let rotated = [&arr[4..5], &arr[0..4]].concat(); -> Option C

4. Quick Check:

   Right rotate by 1 = last element + rest [OK]

Hint: Right rotate by 1 = last element + rest [OK]

Common Mistakes:

• Using wrong slice indices
• Concatenating slices in wrong order
• Confusing left and right rotation slices

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

let arr = vec![10, 20, 30, 40, 50];
let k = 2;
let n = arr.len();
let rotated: Vec<_> = arr.iter().cycle().skip(n - k).take(n).cloned().collect();
println!("{:?}", rotated);

medium

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

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

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

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

Solution

1. Step 1: Understand rotation logic in code

   Code cycles array, skips n-k=3 elements, then takes n=5 elements, effectively right rotating by 2.

2. Step 2: Trace elements after skipping 3

   Skipping first 3 elements: 10,20,30 skipped; next elements are 40,50, then cycle back 10,20,30.

3. Step 3: Collect 5 elements

   Elements collected: 40, 50, 10, 20, 30.

4. Final Answer:

   [40, 50, 10, 20, 30] -> Option D

5. Quick Check:

   Right rotate by 2 = last 2 elements front [OK]

Hint: Cycle and skip n-k for right rotation [OK]

Common Mistakes:

• Confusing skip count with k
• Mixing left and right rotation logic
• Not using cycle iterator correctly

4. The following Rust function is intended to left rotate an array by k positions. What is the bug?

fn left_rotate(arr: &mut [i32], k: usize) {
    let n = arr.len();
    for i in 0..k {
        let temp = arr[i];
        arr[i] = arr[n - k + i];
        arr[n - k + i] = temp;
    }
}

medium

A. It swaps wrong elements; rotation logic is incorrect

B. It causes index out of bounds error

C. It reverses the array instead of rotating

D. It does nothing because loop range is zero

Solution

1. Step 1: Analyze the swapping logic

   The code swaps arr[i] with arr[n-k+i], which does not achieve left rotation but swaps wrong pairs.

2. Step 2: Understand correct rotation method

   Left rotation requires shifting elements left and moving first k elements to end, not swapping like this.

3. Final Answer:

   It swaps wrong elements; rotation logic is incorrect -> Option A

4. Quick Check:

   Incorrect swap logic = wrong rotation [OK]

Hint: Rotation needs shift + append, not simple swaps [OK]

Common Mistakes:

• Swapping instead of shifting elements
• Using wrong indices for swapping
• Assuming swap equals rotation

5. Given an array arr = [1, 2, 3, 4, 5, 6], how can you rotate it left by 4 positions using Rust slice operations without extra space?

hard

A. Reverse first 4 elements, reverse last 2 elements, reverse entire array

B. Reverse last 4 elements, reverse first 2 elements, reverse entire array

C. Reverse entire array, reverse last 2 elements, reverse first 4 elements

D. Reverse first 2 elements, reverse last 4 elements, reverse entire array

Solution

1. Step 1: Understand rotation by reversal method

   Left rotate by k means reverse first k elements, reverse remaining, then reverse whole array.

2. Step 2: Apply to k=4, n=6

   Reverse first 4 elements [1,2,3,4], reverse last 2 elements [5,6], then reverse entire array.

3. Final Answer:

   Reverse first 4 elements, reverse last 2 elements, reverse entire array -> Option A

4. Quick Check:

   Rotation by reversal = reverse k, reverse n-k, reverse all [OK]

Hint: Rotate left k = reverse first k, reverse rest, reverse all [OK]

Common Mistakes:

• Reversing in wrong order
• Mixing k and n-k segments
• Using extra space instead of in-place reversal