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

<?php

    require_once 'vendor/autoload.php';

    use Rindow\Math\Matrix\MatrixOperator;
    
    // Initialize the Matrix Operator
    $mo = new MatrixOperator();
    
    function boundaryTraversal($mat) {
        global $mo;
    
        //Determine dimensions automatically via the shape() method
        $shape = $mat->shape();
        $n = $shape[0];
        $m = $shape[1];
        
        // Traverse the top row
        for ($j = 0; $j < $m-1; $j++) {
            echo($mat[0][$j] . ", ");
        }

        // Traverse the last column
        for ($i = 0; $i < $n-1; $i++) {
            echo($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--) {
                echo($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--) {
                echo($mat[$i][0] . ", ");
            }
        }
    
        echo PHP_EOL;
    }  

  //main area
    $mat = $mo->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).