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

Problem

Given a matrix mat[][] of size n × m, the task is to traverse the boundary elements in clockwise order, starting from the top-left element.

Example 1: 
Input:  mat[][] = [[1, 2, 3, 4], 
                   [5, 6, 7, 8], 
                   [1, 2, 3, 4],
                   [5, 6, 7, 9]]
                   
Output: [1, 2, 3, 4, 8, 4, 9, 7, 6, 5, 1, 5] 

Example 2:
Input: mat[][] = [[1, 2], 
                  [3, 4]]
                  
Output: [1, 2, 4, 3]

Do it in O(n + m) time and not O(n x m) time.

Solution in O(n + m) Time

Algorithm

- Traverse the top row from left to right, excluding the last element on the right.
- Traverse the rightmost column from top to bottom, excluding the last element at the bottom.
- Traverse the bottom row from right to left, excluding the first element on the left.
- Traverse the leftmost column from bottom to top, excluding the first element at the top.

Program in O(n+m) Time

The program is (read through the code and comments):

fn boundary_traversal(mat: &Vec<Vec<i32>>) {
    // Determine dimensions automatically
    let n = mat.len();
    let m = mat[0].len();

    // Traverse the top row
    for j in 0..(m - 1) {
        print!("{}, ", mat[0][j]);
    }

    // Traverse the last column
    for i in 0..(n - 1) {
        print!("{}, ", mat[i][m - 1]);
    }

    // Traverse the bottom row
    if n > 1 {    // Check to avoid duplicating row in single-row matrix
        for j in (1..m).rev() {
            print!("{}, ", mat[n - 1][j]);
        }
    }

    // Traverse the first column
    if m > 1 {    // Check to avoid duplicating column in single-column matrix
        for i in (1..n).rev() {
            print!("{}, ", mat[i][0]);
        }
    }

    println!();
}

fn main() {
    let mat: Vec<Vec<i32>> = vec![
        vec![1, 2, 3, 4],
        vec![5, 6, 7, 8],
        vec![1, 2, 3, 4],
        vec![5, 6, 7, 9],
    ];

    // Pass the matrix as a reference
    boundary_traversal(&mat);
}

The output is:

    1, 2, 3, 4, 8, 4, 9, 7, 6, 5, 1, 5, 

The time complexity is actually O(n+n + (m-1)+(m-1)) = O(2n + 2(m-2)). If the coefficients (multiplicands) of 2 are ignored, as it is customary, then the time complexity would be quoted as O(n + (m-2)). Note: -1, -2, +1, +2, etc. are usually ignored as well. So the time complexity is quoted as O(n+m).

The space complexity is O(n x m), for the input matrix. The matrix in the calling function and the called function are the same (same reference).