The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Reversing an vector means, rearranging the elements such that the last element becomes the first, the last-but-one element becomes the second, the third-to-the-last element becomes third; and so on.

Example:

Input:  [0, 1, 2, 3, 4, 5, 6, 7]  
Output:  [7, 6, 5, 4, 3, 2, 1, 0]

The number of elements in this example is even. If the number of elements is odd, the middle (center) element will not change its position.

An vector can be reversed, using the temporary-vector-technique, two pointers or single pointer.

Reversing an Vector using Temporary Vector in O(n) Time and O(n) Space

Here is the brute-force (naive) approach.

This involves:

- Creating a temporary vector of same size as the original vector;
- copying all elements from original vector to the temporary vector in reverse order;
- and finally, copying all the elements from temporary vector back to the original vector.

The algorithm essentially, takes the last element and put as the first element, takes the last-but-one element and puts as the second element, takes the third-to-the-last element and puts as the third element; and so on. This swapping continues until the middle of the vector is reached. If the number of elements in the vector is odd, then the middle element is not swapped.

With zero based indexing, the swapping statement is:

     temp[i] = arr[n - i - 1];

where i is the iterating index from 0, and n is the length (size) of the vector.

When i=0, "temp[0] = arr[n - 0 – 1];" => "temp[0] = arr[n – 1];"
When i=1, "temp[1] = arr[n - 1 – 1];" => "temp[1] = arr[n – 2];"
When i=2, "temp[2] = arr[n - 2 – 1];" => "temp[1] = arr[n - 3];"

The following program illustrates this (read through the code and comments):

    fn reverse_array(vtr: &mut Vec<i32>) {    //use reference to avoid unnecessary recopying of vector
        let n = vtr.len();
    
        // Temporary vector to store elements
        // in reversed order
        let mut temp = vec![0; n];
  
        // Copy all elements from original vector
        // to temp in reverse order
        for i in 0..n {
            temp[i] = vtr[n - i - 1];
        }
  
        // Copy elements back to original vector
        for i in 0..n {
            vtr[i] = temp[i];
        }
    }

fn main() {
    let mut vtr = vec![0, 1, 2, 3, 4, 5, 6, 7];
        
    reverse_array(&mut vtr);    //use reference to avoid unnecessary recopying of vector
            
    for i in 0..vtr.len() {
        print!("{} ", vtr[i]);
    }
    println!();
}

The output is:

    7 6 5 4 3 2 1 0 

achieved in O(n) time and O(n) space for the for-loops and arrays respectively. The time complexity is actually O(2n) and the space complexity is actually O(2n). However, the coefficient (multiplier) is usually omitted when quoting the complexity.

The given vector and the vector in the reverseArray() function parameter list (parentheses) are the same one vector (references).

Reversing an Vector using Two Pointers in O(n) Time and O(n) Space

Two pointers refer to left (i) and right (j) indexes, such that left points at the start of the vector and right points to the end of the vector, initially.

While the left pointer is less than the right pointer, swap the elements at these two positions. After each swap, increment the left pointer and decrement the right pointer to move towards the center of the vector. This will swap all the elements in the first half with their corresponding elements in the second half.

The following program illustrates this (read through the code and comments):

    // Helper function to swap two numbers
    fn swap(vtr: &mut Vec<i32>, a: usize, b: usize) {    //use reference to avoid unnecessary recopying of vector
        let temp = vtr[a];    // temporary single variable and not temporary vector
        vtr[a] = vtr[b];
        vtr[b] = temp;
    }

    fn reverse_array(vtr: &mut Vec<i32>) {    //use reference to avoid unnecessary recopying of vector
        let n = vtr.len();
    
        let mut left = 0; let mut right = n - 1;

        // Iterate till left would almost equal right
        while left < right {
            swap(vtr, left, right);

            // Increment the left pointer
            left += 1;
            // Decrement the right pointer
            right -= 1;
        }
    }

fn main() {
    let mut vtr = vec![0, 1, 2, 3, 4, 5, 6, 7];
        
    reverse_array(&mut vtr);    //use reference to avoid unnecessary recopying of vector
            
    for i in 0..vtr.len() {
        print!("{} ", vtr[i]);
    }
    println!();
}

Note the use of the swap() helper function, where int *a from the swap() function corresponds to &arr[left] in the called function, and int *b from the swap() function corresponds to &arr[right] in the called function. The whole program has just one vector, given in the main section. The output is:

    7 6 5 4 3 2 1 0 

achieved in O(n) time and O(n) space, for the for-loop and vector respectively. O(n) space refers to the only vector, which is the input vector. The while-loop takes precisely O(1/2N) time, but the ½ (coefficient) has to be omitted when quoting the complexity.

Reversing an Vector using Single Pointer in O(n) Time and O(n) Space

This algorithm iterates over the first half of the vector and swaps each element with its corresponding element of the second half. So, while iterating over the first half, any element at index i is swapped with the element at index (n - i – 1). If the number of elements in the given vector is odd, the center element is not swapped. left (i) is the single pointer. The following program illustrates this (read through the code and comments):

    fn reverse_array(vtr: &mut Vec<i32>) {    //use reference to avoid unnecessary recopying of vector
        let n = vtr.len();
    
        // swap arr[i] with arr[n - i - 1]
        for i in 0..n/2 {    //integer division
            let temp = vtr[i];    //temporary single variable and not temporary vector
            vtr[i] = vtr[n - i - 1];
            vtr[n - i - 1] = temp;
        }
    }

fn main() {
    let mut vtr = vec![0, 1, 2, 3, 4, 5, 6, 7];
        
    reverse_array(&mut vtr);    //use reference to avoid unnecessary recopying of vector
            
    for i in 0..vtr.len() {
        print!("{} ", vtr[i]);
    }
    println!();
}

n / 2 is integer division. This division discards the remainder. If the number of elements in the vector is odd, say 9 for example, then the center (middle) index would be 4, whose element is not swapped. If the number of elements is even, say 8 for example, then the almost center (middle) left index would be 3, whose element has to be swapped with the almost center (middle) right element of index 4.

The output is:

    7 6 5 4 3 2 1 0 

achieved in O(n) time and O(n) space, for the for-loop and vector respectively. O(n) space refers to the only vector, which is the input vector. The for-loop takes precisely O(1/2N) time, but the ½ has to be omitted when quoting the complexity.

Thanks for reading.