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

import numpy as np

def boundaryTraversal(mat):
    # Determine dimensions automatically
    n = mat.shape[0]
    m = mat.shape[1]
    
    # Traverse the top row
    for j in range(0, m-1):
        print(mat[0,j], end=", ");

    # Traverse the last column
    for i in range(0, n-1): 
        print(mat[i,m-1], end=", ");

    # Traverse the bottom row
    if (n > 1):  # Check to avoid duplicating row in single-row matrix
        for j in range(m - 1, 0, -1):
            print(mat[n-1,j], end=", ");

    # Traverse the first column
    if (m > 1):    # Check to avoid duplicating column in single-column matrix
        for i in range(n - 1, 0, -1):
            print(mat[i,0], end=", ");
    
    print();
    
#main area
mat = np.array([[1, 2, 3, 4], [5, 6, 7, 8], [1, 2, 3, 4], [5, 6, 7, 9]])

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