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

Rotating an vector, right, is the same as rotating the vector clockwise. Three ways of rotating the vector, right, will be explained in this tutorial, beginning with rotating the vector one-by-one.

Consider the following vector:

    [0, 1, 2, 3, 4, 5, 6, 7]  

If the vector is rotated right by 3 places, then the vector would become:

    [5, 6, 7, 0, 1, 2, 3, 4]  

Rotation in the vector is defined as the process of rearranging the elements in the vector by shifting each element to a new position, by same distance. The elements towards the end, cycle to the front of the vector.

The letter, d can be used as the number of shifts. d can be 0; it can be 1; it can be 2; it can be 3; it can be 4; etc.

Rotate Right, One-by-One

This is the brute-force (naive) approach.

Task

Rotate the following vector, right by d=3 positions:

    [0, 1, 2, 3, 4, 5, 6, 7] 

Do it in a time complexity of O(n x d) and a space complexity of O(n), where n is the size (length) of the vector and d is the number of rotating positions.

Illustration

The given vector is:

    [0, 1, 2, 3, 4, 5, 6, 7]

For the first position shift, the vector becomes:

    [7, 0, 1, 2, 3, 4, 5, 6]

For the second position shift, the vector becomes:

    [6, 7, 0, 1, 2, 3, 4, 5]

For the third position shift, the vector becomes:

    [5, 6, 7, 0, 1, 2, 3, 4]

The following program does the rotation with d=3 (read through the code and comments):

    fn right_rotate_arr(vtr: &mut Vec<i32>, d: usize) {    //use reference to avoid unnecessary recopying of vector
        let n = vtr.len();
    
        // Repeat the rotation d times
        for _ in 0..d {
            // Right rotate the vector by one position
            let last = vtr[n - 1];
            for j in (1..n).rev() {
                vtr[j] = vtr[j - 1];
            }
            vtr[0] = last;      
        }
    }

fn main() {
    let mut vtr = vec![0, 1, 2, 3, 4, 5, 6, 7];
    let d = 3;

    right_rotate_arr(&mut vtr, d);    //use reference to avoid unnecessary recopying of vector
  
    for i in 0..vtr.len() {
        print!("{} ", vtr[i]);
    }
    println!();
}

The outer for-loop does 3 iterations corresponding to d=3. At the beginning of the outer for-loop, the last element of the vector is first recorded. The inner for-loop then shifts each element up by one place. The last element is then put in the position of the first element, at the bottom of the outer for-loop, outside the inner for-loop (but inside the outer for-loop). This process is repeated 3 times for d=3.

The output is:

    5 6 7 0 1 2 3 4 

as expected.

Rotate Right Using Temporary Vector

This approach uses a temporary vector of size n, where n is the length of the original vector. If the vector is rotated right by d positions, the last d elements will be in the beginning of the vector, and the first (n - d) elements will take the rest of the vector to the end, in order.

Algorithm Summary

- Copy the last d elements of the original vector into the first d positions of the temporary vector.
- Then copy the first n - d elements of the original vector to the right part of the temporary vector.
- Finally, copy all the elements of temporary vector back into the original vector.

Task

Repeat the above problem for a time complexity of O(n) and space complexity of O(n), using temporary vector.

The following program does the rotation with d=3 (read through the code and comments):

    fn right_rotate_arr(vtr: &mut Vec<i32>, d: usize) {    //use reference to avoid unnecessary recopying of vector
        let n = vtr.len();
    
        // Handle case when d > n
        let d = d % n;    //modulus
  
        // To store rotated version of vector
        let mut temp = vec![0; n];

        // Copy last d elements to the front of temp
        for i in 0..d {
            temp[i] = vtr[n - d + i];
        }

        // Copy the first n - d elements to the back of temp
        for i in 0..(n - d) {
            temp[i + d] = vtr[i];
        }

        // Copy the elements of temp in arr to get the 
        // final rotated vector
        for i in 0..n {
            vtr[i] = temp[i];
        }
    }

fn main() {
    let mut vtr = vec![0, 1, 2, 3, 4, 5, 6, 7];
    let d = 3;

    right_rotate_arr(&mut vtr, d);    //use reference to avoid unnecessary recopying of vector
  
    for i in 0..vtr.len() {
        print!("{} ", vtr[i]);
    }
    println!();
}

The output is:

    5 6 7 0 1 2 3 4 

as expected.

The time complexity is O(n) as the first two for-loops compliment one another. The space complexity is actually O(2n), but the coefficient (multiplier of 2) is omitted when quoting complexity.

Rotate Right Using Reversal Algorithm

This approach is based on the observation that if the vector is rotated right by d positions, the last d elements will be in the front and the first (n - d) elements will be in the right part, to the end of the vector.

Algorithm Summary

- First reverse all the elements of the vector.
- Then reorder the first d elements by reversing them.
- Finally, reorder the rest of the (n - d) elements, by reversing them, to get the complete rotated vector.

Task

Repeat the above problem for a time complexity of O(n) and space complexity of O(n), using Reversal Algorithm.

The following program does the rotation with d=3 (read through the code and comments):

    fn reverse(vtr: &mut Vec<i32>, mut start: usize, mut end: usize) {
        while start < end {
            let temp = vtr[start];    //temporary variable of O(1) space
            vtr[start] = vtr[end];
            vtr[end] = temp;
            start += 1;
            end -= 1;
        }
    }

    fn right_rotate_arr(vtr: &mut Vec<i32>, d: usize) {    //use reference to avoid unnecessary recopying of vector
        let n = vtr.len();
    
        // Handle the case where d > size of vector
        let d = d % n;    //modulus
  
        // Reverse the entire vector
        reverse(vtr, 0, n - 1);

        // Reverse the first d elements
        reverse(vtr, 0, d - 1);

        // Reverse the remaining n-d elements
        reverse(vtr, d, n - 1);
    }

fn main() {
    let mut vtr = vec![0, 1, 2, 3, 4, 5, 6, 7];
    let d = 3;

    right_rotate_arr(&mut vtr, d);    //use reference to avoid unnecessary recopying of vector
  
    for i in 0..vtr.len() {
        print!("{} ", vtr[i]);
    }
    println!();
}

The output is:

    5 6 7 0 1 2 3 4 

as expected.

The time complexity is actually O(2n) for the overall two reversals, but the coefficient (multiplier of 2) is omitted when quoting complexity. The space complexity is O(n). The helper function reverse(), used a space of O(1), which is ignored.

What Approach to choose

Choose the approach with the least actual time complexity or least actual space complexity, or both. The Rotate Right, One-by-One is definitely not the approach to choose, because of its high time complexity of O(n x d).

Left (Counter Clockwise) Rotation

This is left as exercises for the reader. The reader should repeat all the above 3 exercises for left rotation.

Thanks for reading.