Array Rotation Techniques in DSA Rust - Execution Trace

Concept Flow - Array Rotation Techniques

Start with array

↓

Choose rotation direction

↓

Rotate Left

↓

Shift elements

↓

Wrap around shifted out elements

↓

Resulting rotated array

This flow shows how an array is rotated either left or right by shifting elements and wrapping the shifted out elements back.

Execution Sample

DSA Rust

let arr = [1, 2, 3, 4, 5];
let k = 2;
// Rotate left by k
let rotated = rotate_left(arr, k);
println!("{:?}", rotated);

Rotate the array [1,2,3,4,5] left by 2 positions.

Execution Table

Step	Operation	Array State	Pointer Changes	Visual State
1	Start with original array	[1, 2, 3, 4, 5]	head=0	1 -> 2 -> 3 -> 4 -> 5
2	Rotate left by 1 (shift elements left by 1)	[2, 3, 4, 5, 5]	head=1	2 -> 3 -> 4 -> 5 -> 5
3	Wrap first element (1) to end	[2, 3, 4, 5, 1]	head=1	2 -> 3 -> 4 -> 5 -> 1
4	Rotate left by 2 (repeat shift and wrap)	[3, 4, 5, 1, 1]	head=2	3 -> 4 -> 5 -> 1 -> 1
5	Wrap second element (2) to end	[3, 4, 5, 1, 2]	head=2	3 -> 4 -> 5 -> 1 -> 2
6	Rotation complete	[3, 4, 5, 1, 2]	head=2	3 -> 4 -> 5 -> 1 -> 2

💡 Rotation by 2 completed, array rotated left by 2 positions.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
arr	[1, 2, 3, 4, 5]	[2, 3, 4, 5, 5]	[2, 3, 4, 5, 1]	[3, 4, 5, 1, 1]	[3, 4, 5, 1, 2]	[3, 4, 5, 1, 2]
head	0	1	1	2	2	2

Key Moments - 3 Insights

Why do we wrap the shifted out element to the end instead of discarding it?

Because rotation means elements shifted out from one end come back at the other end, preserving all elements. See steps 3 and 5 in execution_table where the first and second elements are wrapped to the end.

Why does the array temporarily have duplicate values during shifting?

During shifting, elements move left and the last position duplicates the last shifted value temporarily before wrapping. This is shown in steps 2 and 4 where the last element is repeated before wrapping.

How do we know when rotation is complete?

Rotation completes after shifting and wrapping k times. Step 6 in execution_table shows the final rotated array after 2 rotations.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after step 3?

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

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

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

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

💡 Hint

Check the 'Array State' column for step 3 in execution_table.

At which step does the pointer 'head' change to 2?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the 'Pointer Changes' column in execution_table and variable_tracker.

If we rotate left by 1 instead of 2, what would be the final array state?

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

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

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

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

💡 Hint

Refer to step 3 in execution_table which shows rotation by 1.

Concept Snapshot

Array Rotation Techniques:
- Rotate left: shift elements left, wrap shifted out to end.
- Rotate right: shift elements right, wrap shifted out to start.
- Repeat shift and wrap k times for rotation by k.
- Preserves all elements, no data lost.
- Useful for cyclic shifts in arrays.

Full Transcript

This visualization shows how to rotate an array left by k positions. Starting with the original array, each rotation shifts elements left by one and wraps the first element to the end. This process repeats k times. The execution table tracks the array state and pointer changes at each step. Key moments clarify why wrapping is needed and how temporary duplicates appear during shifting. The visual quiz tests understanding of array states and pointer positions during rotation. The snapshot summarizes the rotation technique as shifting and wrapping elements to achieve cyclic 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