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):

    boundaryTraversal <- function(mat) {
        # Determine dimensions automatically
        n = nrow(mat);
        m = ncol(mat);
    
        # Traverse the top row
        for (j in 1:m) {
            cat(mat[1,j], ", ", sep="");
        }

        # Traverse the last column
        for (i in 2:n) {
            cat(mat[i, m], ", ", sep="");
        }

        # Traverse the bottom row
        if (n > 2) {    # Check to avoid duplicating row in single-row matrix
            for (j in (m-1):2) {
                cat(mat[n, j], ", ", sep="");
            }
        }

        # Traverse the first column
        if (m > 2) {    # Check to avoid duplicating column in single-column matrix
            for (i in n:2) {
                cat(mat[i,1], ", ", sep="");
            }
        }
    
        cat("\n");
    }

# Main area
    mat <- matrix(c(1, 2, 3, 4,
                    5, 6, 7, 8,
                    1, 2, 3, 4,
                    5, 6, 7, 9), nrow = 4, ncol = 4, byrow = TRUE)

    boundaryTraversal(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).