Array Reversal Techniques in DSA Rust

Mental Model

Reversing an array means flipping its order so the last element becomes first and the first becomes last.

Analogy: Imagine a row of books on a shelf. Reversing the array is like taking the books from both ends and swapping them until you reach the middle.

[1] -> [2] -> [3] -> [4] -> [5] -> null
↑start                 ↑end

Dry Run Walkthrough

Input: array: [1, 2, 3, 4, 5]

Goal: Reverse the array so it becomes [5, 4, 3, 2, 1]

Step 1: swap elements at start=0 and end=4

[5, 2, 3, 4, 1]

Why: Swap first and last to start reversing the order

Step 2: move start to 1 and end to 3

[5, 2, 3, 4, 1]
 ↑start     ↑end

Why: Move inward to swap next pair

Step 3: swap elements at start=1 and end=3

[5, 4, 3, 2, 1]

Why: Swap second and second last elements

Step 4: move start to 2 and end to 2

[5, 4, 3, 2, 1]
       ↑start,end

Why: Pointers meet in the middle, reversal complete

Result:

[5, 4, 3, 2, 1]

Annotated Code

DSA Rust

fn reverse_array(arr: &mut [i32]) {
    let mut start = 0;
    let mut end = arr.len().saturating_sub(1);
    while start < end {
        arr.swap(start, end); // swap elements at start and end
        start += 1; // move start pointer forward
        end = end.saturating_sub(1); // move end pointer backward
    }
}

fn main() {
    let mut arr = [1, 2, 3, 4, 5];
    reverse_array(&mut arr);
    for val in arr.iter() {
        print!("{} ", val);
    }
    println!();
}

arr.swap(start, end); // swap elements at start and end

exchange values at current start and end positions

start += 1; // move start pointer forward

advance start index to next element

end = end.saturating_sub(1); // move end pointer backward

decrease end index to previous element safely

while start < end {

continue swapping until pointers meet or cross

Output

5 4 3 2 1 

Complexity Analysis

Time: O(n) because each element is visited once during swapping

Space: O(1) because reversal is done in place without extra storage

vs Alternative: Naive approach creates a new array and copies elements in reverse order, costing O(n) extra space; this in-place method saves memory

Edge Cases

empty array

function does nothing, array remains empty

DSA Rust

while start < end {

single element array

no swaps occur, array stays the same

DSA Rust

while start < end {

array with duplicate elements

duplicates are swapped like any other elements, reversal is correct

DSA Rust

arr.swap(start, end);

When to Use This Pattern

When you need to reverse the order of elements in a list or array efficiently, use the two-pointer swapping technique to do it in place.

Common Mistakes

Mistake: Using a loop that goes through the entire array length instead of stopping at the middle
Fix: Stop swapping when start pointer meets or passes end pointer to avoid undoing swaps

Mistake: Not swapping elements correctly, e.g., assigning instead of swapping
Fix: Use a swap method or temporary variable to exchange values properly

Summary

Reverses an array by swapping elements from both ends moving inward.

Use when you want to reverse the order of elements efficiently without extra space.

The key insight is swapping pairs from the outside towards the center until pointers meet.

Practice

1. What does reversing an array mean in simple terms?

easy

A. Changing the order of elements so the last becomes first and first becomes last

B. Sorting the array in ascending order

C. Removing duplicate elements from the array

D. Adding new elements to the end of the array

Solution

1. Step 1: Understand array reversal

   Reversing means flipping the order of elements so the last element comes first and the first element goes last.

2. Step 2: Compare with other options

   Sorting arranges elements by value, removing duplicates deletes repeats, and adding elements is insertion, not reversal.

3. Final Answer:

   Changing the order of elements so the last becomes first and first becomes last -> Option A

4. Quick Check:

   Reversal = Flip order [OK]

Hint: Reversal flips order, not sorting or adding [OK]

Common Mistakes:

• Confusing reversal with sorting
• Thinking reversal removes elements
• Mixing reversal with adding elements

2. Which of the following Rust code snippets correctly reverses a mutable array arr in place?

easy

A. arr = arr.reverse();

B. arr.reverse();

C. arr.reverse(&mut arr);

D. reverse(arr);

Solution

1. Step 1: Identify correct method usage

   In Rust, the reverse() method is called directly on a mutable slice or array as arr.reverse(); to reverse it in place.

2. Step 2: Check other options for errors

   arr = arr.reverse(); tries to assign the result of reverse() which returns (), so it's invalid. arr.reverse(&mut arr); passes &mut arr as argument, but reverse() takes no arguments. reverse(arr); calls a function reverse which is undefined.

3. Final Answer:

   arr.reverse(); -> Option B

4. Quick Check:

   Use method directly on mutable array [OK]

Hint: Use arr.reverse() without assignment or arguments [OK]

Common Mistakes:

• Assigning reverse() result to array
• Passing array as argument to reverse()
• Calling undefined reverse function

3. What will be the output of this Rust code?

let mut arr = [1, 2, 3, 4, 5];
arr.reverse();
println!("{:?}", arr);

medium

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

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

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

D. Compilation error

Solution

1. Step 1: Understand reverse() effect on array

   The reverse() method reverses the array elements in place, so the order becomes last to first.

2. Step 2: Apply reverse to given array

   Original array is [1, 2, 3, 4, 5]. After reversal, it becomes [5, 4, 3, 2, 1].

3. Final Answer:

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

4. Quick Check:

   Reverse flips array order [OK]

Hint: Reverse flips array elements order [OK]

Common Mistakes:

• Expecting original order after reverse
• Thinking reverse sorts array
• Confusing output format

4. Identify the error in this Rust code that tries to reverse an array:

let arr = [10, 20, 30, 40];
arr.reverse();

medium

A. Cannot call reverse() on an immutable array

B. reverse() method does not exist for arrays

C. Missing semicolon after array declaration

D. reverse() requires an argument

Solution

1. Step 1: Check mutability of array

   The array arr is declared immutable by default with let. The reverse() method requires a mutable array.

2. Step 2: Understand method requirements

   To reverse in place, the array must be mutable, declared as let mut arr. Otherwise, calling reverse() causes a compile error.

3. Final Answer:

   Cannot call reverse() on an immutable array -> Option A

4. Quick Check:

   reverse() needs mutable array [OK]

Hint: Make array mutable with 'mut' before reversing [OK]

Common Mistakes:

• Forgetting to add 'mut' to array declaration
• Thinking reverse() needs arguments
• Assuming reverse() is not available for arrays

5. Given a vector vec = vec![1, 2, 3, 4, 5], which code snippet correctly reverses it and returns a new reversed vector without modifying the original?

hard

A. let rev_vec = vec.into_iter().reverse().collect();

B. vec.reverse(); let rev_vec = vec.clone();

C. let rev_vec = vec.reverse();

D. let rev_vec = vec.iter().rev().cloned().collect::();

Solution

1. Step 1: Understand vector reversal without mutation

   To reverse without changing original, use iterator rev() on iter(), clone elements, then collect into new vector.

2. Step 2: Analyze options

   let rev_vec = vec.iter().rev().cloned().collect::(); uses vec.iter().rev().cloned().collect() which creates a new reversed vector. vec.reverse(); let rev_vec = vec.clone(); reverses original vector in place, modifying it. let rev_vec = vec.reverse(); tries to assign reverse() result which is (), invalid. let rev_vec = vec.into_iter().reverse().collect(); uses into_iter() which consumes the original vector, so it doesn't leave the original unmodified.

3. Final Answer:

   let rev_vec = vec.iter().rev().cloned().collect::(); -> Option D

4. Quick Check:

   Use iter().rev().cloned().collect() for new reversed vector [OK]

Hint: Use iter().rev().cloned().collect() for reversed copy [OK]

Common Mistakes:

• Modifying original vector instead of copying
• Assigning reverse() result directly
• Using invalid reverse() on iterator