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

package main

import (
    "fmt"
)

    func boundaryTraversal(mat *[4][4]int) {    //use pointer to avoid unnecessary function recopying of Array
        // Determine dimensions automatically
        var n = len(*mat)
        var m = len((*mat)[0])
        
        // Traverse the top row
        for j := 0; j < m-1; j++ {
            fmt.Print((*mat)[0][j], ", ");
        }

        // Traverse the last column
        for i := 0; i < n-1; i++ {
            fmt.Print((*mat)[i][m-1], ", ");
        }

        // Traverse the bottom row
        if (n > 1) {    // Check to avoid duplicating row in single-row matrix
            for j := m - 1; j > 0; j-- {
                fmt.Print((*mat)[n-1][j], ", ");
            }
        }

        // Traverse the first column
        if (m > 1) {    // Check to avoid duplicating column in single-column matrix
            for i := n - 1; i > 0; i-- {
                fmt.Print((*mat)[i][0], ", ");
            }
        }
    
        fmt.Println();
    } 

func main() {
    var mat = [4][4]int{{1, 2, 3, 4}, 
                        {5, 6, 7, 8}, 
                        {1, 2, 3, 4},
                        {5, 6, 7, 9}};

    boundaryTraversal(&mat);    //use pointer to avoid unnecessary function recopying of Array
}

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