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

def boundary_traversal(mat)
  # Determine dimensions automatically
  n = mat.length
  m = mat[0].length

  # Traverse the top row
  for j in 0...m-1
    print "#{mat[0][j]}, "
  end

  # Traverse the last column
  for i in 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 (1..(m-1)).to_a.reverse
      print "#{mat[n-1][j]}, "
    end
  end

  # Traverse the first column
  if m > 1    # Check to avoid duplicating column in single-column matrix
    for i in (1..(n-1)).to_a.reverse
      print "#{mat[i][0]}, "
    end
  end

  puts
end

# Main area
mat = [
       [1, 2, 3, 4],
       [5, 6, 7, 8],
       [1, 2, 3, 4],
       [5, 6, 7, 9]
     ]

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