Why Array Rotation Techniques in DSA Rust?

The Big Idea

What if you could move hundreds of items in an array instantly without moving each one by hand?

The Scenario

Imagine you have a row of books on a shelf, and you want to move the first few books to the end without taking each book out and placing it one by one.

Doing this by hand for a large number of books is tiring and slow.

The Problem

Manually moving each book one by one takes a lot of time and effort.

It is easy to lose track or make mistakes, like placing books in the wrong order.

For computers, doing this with many items without a smart method wastes time and memory.

The Solution

Array rotation techniques let us move parts of the array efficiently.

They help shift elements in a smart way without moving each item one by one.

This saves time and keeps the order correct.

Before vs After

✗ Before

let mut arr = [1, 2, 3, 4, 5];
for _ in 0..2 {
    let first = arr[0];
    for i in 0..arr.len()-1 {
        arr[i] = arr[i+1];
    }
    arr[arr.len()-1] = first;
}

✓ After

fn rotate_array(arr: &mut [i32], k: usize) {
    let n = arr.len();
    let k = k % n;
    arr.reverse();
    arr[..n - k].reverse();
    arr[n - k..].reverse();
}

let mut arr = [1, 2, 3, 4, 5];
rotate_array(&mut arr, 2);

What It Enables

It enables fast and reliable shifting of data in arrays, making many algorithms and tasks efficient.

Real Life Example

In music playlists, rotating the list lets you start playing from a different song without changing the order of the rest.

Key Takeaways

Manual shifting is slow and error-prone.

Rotation techniques use smart steps to move parts of arrays quickly.

They help in many real-world tasks like scheduling and data processing.

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