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 x m, the task is to print all elements of the matrix in spiral form, as shown in the following figure:

Employ boundary traversal technique.

Example: 
Input: mat[][] = {{1,  2,  3,  4,  5}, 
                  {14, 15, 16, 17, 6},
                  {13, 20, 19, 18, 7},
                  {12, 11, 10, 9,  8}};

The input numbers have been given in spiral form, and should just be read.

Output : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Solution

The algorithm is as follows:

- Traverse the top row from j=0 to j=m-2.
- Traverse the rightmost column from i=0 to i=n-2.
- Traverse the bottom row from j=m-1 to j=1.
- Traverse the leftmost column from i=n-1 to i=1.

- Traverse the second row from j=2 to j=m-3.
- Traverse the last-but-one rightmost column from i=1 to i=n-3.
- Traverse the last-but-one bottom row from j=m-2 to j=2.
- Traverse the second leftmost column from i=n-2 to i=2.

- Traverse the third row from j=3 to j=m-4.
- Continue the traversing in the spiral form. - - -
- - - - - -

The program

The program is (read through the code and comments):

def spirallyTraverse(mat, n, m):
    # Let a be the difference between the row being traversed, and i=0.
    # Let b be the difference between the column being traversed, and j=0.
    a = 0
    b = 0
    # Let c be the difference between the bottom of the matrix and the traversing column end element index.
    # Let d be the difference between the right end of the matrix and the traversing row end element index.
    c = 1
    d = 1
         
    totalNumOfElements = n * m
    counter = 0
         
    i = 0; j = 0
    while counter < totalNumOfElements:
        # Traverse top current row from left to right
        start_j = j + b
        end_j = m - d
        for next_j in range(start_j, end_j):
            print(f"{mat[i + b][next_j]}, ", end="")
            counter += 1
        j = end_j if end_j > start_j else start_j
 
        # Traverse last current column from top to bottom
        start_i = i + a
        end_i = n - c
        for next_i in range(start_i, end_i):
            print(f"{mat[next_i][j]}, ", end="")
            counter += 1
        i = end_i if end_i > start_i else start_i
 
        # Traverse current bottom row from right to left
        if n > 1: # Check to avoid duplicating row in single-row matrix
            start_j2 = m - d
            end_j2 = b
            for next_j in range(start_j2, end_j2, -1):
                print(f"{mat[n - c][next_j]}, ", end="")
                counter += 1
            j = end_j2 if start_j2 > end_j2 else start_j2
 
        # Traverse current first column from bottom to top
        if m > 1: # Check to avoid duplicating column in single-column matrix
            start_i2 = n - c
            end_i2 = a
            for next_i in range(start_i2, end_i2, -1):
                print(f"{mat[next_i][j]}, ", end="")
                counter += 1
            i = end_i2 if start_i2 > end_i2 else start_i2
                 
        a += 1; b += 1; c += 1; d += 1
         
    print()

#main area
n = 4    #number of rows
m = 5    #number of columns
mat = [[1,  2,  3,  4,  5],                       
       [14, 15, 16, 17, 6],                      
       [13, 20, 19, 18, 7],                      
       [12, 11, 10, 9,  8]]           
           
spirallyTraverse(mat, n, m)

The output is:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,

The time complexity is actually O(2 n x m), with the first O(n x m) for populating the input matrix with all the elements, and the second O(n x m) for iterating over all the elements in the matrix in the called function. Since the coefficient (multiplicand of 2) is usually omitted, the time complexity is quoted as O(n x m).

The space complexity is O(n x m), for the input matrix, which is the same as the matrix in the called function (same reference).

Thanks for reading.