Array Reversal Techniques in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind reversing an array?

Reversing an array means changing the order of elements so the first becomes last, the second becomes second last, and so on, like flipping a row of books from left to right.

beginner

How does the two-pointer technique work for array reversal?

Use two pointers: one at the start and one at the end. Swap the elements they point to, then move the start pointer forward and the end pointer backward until they meet or cross.

beginner

What is the time complexity of reversing an array using the two-pointer method?

The time complexity is O(n), where n is the number of elements, because each element is visited once during swapping.

intermediate

Show a simple Rust code snippet to reverse an array in place using the two-pointer method.

fn reverse_array(arr: &mut [i32]) {
    let mut start = 0;
    let mut end = arr.len() - 1;
    while start < end {
        arr.swap(start, end);
        start += 1;
        end -= 1;
    }
}

beginner

Why is reversing an array useful in programming?

Reversing arrays helps in problems like undoing actions, palindrome checks, or preparing data in the opposite order, similar to rewinding a tape or flipping a photo album backwards.

What does the two-pointer technique use to reverse an array?

A Sorting the array in descending order

B A temporary array to store reversed elements

C Two indexes, one at start and one at end, swapping elements

D Using recursion to reverse elements

The two-pointer technique swaps elements at the start and end indexes moving inward.

What is the time complexity of reversing an array with the two-pointer method?

A O(1)

B O(n^2)

C O(log n)

D O(n)

Each element is swapped once, so the time complexity is linear, O(n).

In Rust, which method swaps two elements in a mutable slice?

A arr.swap(index1, index2)

B arr.reverse()

C arr.sort()

D arr.push()

The swap method exchanges elements at two indexes in a mutable slice.

What happens if the start pointer crosses the end pointer during reversal?

A Reversal is complete

B Array is sorted

C Array is empty

D Error occurs

When pointers cross, all elements have been swapped and reversal is done.

Which of these is NOT a use case for array reversal?

A Checking if array is a palindrome

B Sorting array in ascending order

C Reversing a string

D Undoing a sequence of actions

Sorting is different from reversing; reversing changes order but does not sort.

Explain how to reverse an array using the two-pointer technique step-by-step.

Think of flipping a row of books from both ends towards the center.

Write a simple Rust function to reverse an array in place and describe how it works.

Use arr.swap(start, end) inside a while loop.

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