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 spirally_traverse(mat)
  # Determine dimensions automatically
  n = mat.length
  m = mat[0].length # Fixed: accurately gets column length

  # 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

  total_num_of_elements = n * m
  counter = 0
  i = 0
  j = 0

  while counter < total_num_of_elements
    # Traverse top current row from left to right
    for j in (j + b)...(m - d)
      print "#{mat[i + b][j]}, "
      counter += 1
    end
    j = m - d    # Match termination state: j becomes m - d

    # Traverse last current column from top to bottom
    for i in (i + a)...(n - c)
      print "#{mat[i][j]}, "
      counter += 1
    end
    i = n - c    # Match termination state: i becomes n - c

    # Traverse current bottom row from right to left
    if n > 1    # Check to avoid duplicating row in single-row matrix
      for j in (b + 1..m - d).to_a.reverse
        print "#{mat[n - c][j]}, "
        counter += 1
      end
      j = b    # Match termination state: j becomes b
    end

    # Traverse current first column from bottom to top
    if m > 1    # Check to avoid duplicating column in single-column matrix
      for i in (a + 1..n - c).to_a.reverse
        print "#{mat[i][j]}, "
        counter += 1
      end
      i = a    # Match termination state: i becomes a
    end

    a += 1; b += 1; c += 1; d += 1
  end
  puts
end

# main area
mat = [[1, 2, 3, 4, 5],
       [14, 15, 16, 17, 6],
       [13, 20, 19, 18, 7],
       [12, 11, 10, 9, 8]]

spirally_traverse(mat)

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.