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

#include <stdio.h>

void boundaryTraversal(int mat[][4], int n, int m) {
    // Traverse the top row
    for (int j = 0; j < m-1; j++) {
        printf("%i, ", mat[0][j]);
    }

    // Traverse the last column
    for (int i = 0; i < n-1; i++) {
        printf("%i, ", mat[i][m-1]);
    }

    // Traverse the bottom row
    if (n > 1) { // Check to avoid duplicating row in single-row matrix
        for (int j = m - 1; j > 0; j--) {
            printf("%i, ", mat[n-1][j]);
        }
    }

    // Traverse the first column
    if (m > 1) { // Check to avoid duplicating column in single-column matrix
        for (int i = n - 1; i > 0; i--) {
            printf("%i, ", mat[i][0]);
        }
    }
    
    printf("\n");
}

int main(int argc, char **argv) 
{
    int n=4, m=4;
    int mat[4][4] = {{1, 2, 3, 4}, 
                     {5, 6, 7, 8}, 
                     {1, 2, 3, 4},
                     {5, 6, 7, 9}};
                    
    boundaryTraversal(mat, n, m);

    return 0;
}

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