Spiral Matrix

This question was asked during my second round interview with Yahoo search team.

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

My Solution

This is pretty straight forward O(mn) solution by traversing right, down, left, and up until it reaches the center. But careful with the duplication by restricting left and up traversal with the start/end indexes.

def spiral_order(matrix):
  if not matrix:
    return []
  res = []
  rowStart, rowEnd = 0, len(matrix)
  colStart, colEnd = 0, len(matrix[0])

  # traverse until the center matrix
  while rowStart < rowEnd and colStart < colEnd:
    # traverse right
    for i in range(colStart, colEnd):
      res.append(matrix[rowStart][i])
    rowStart += 1

    # traverse down
    for j in range(rowStart, rowEnd):
      res.append(matrix[j][colEnd-1])
    colEnd -= 1

    # traverse left, careful on the duplication
    if rowStart < rowEnd:
      for k in range(colEnd-1, colStart-1, -1):
        res.append(matrix[rowEnd-1][k])
    rowEnd -= 1

    # traverse up, careful on the duplication
    if colStart < colEnd:
      for l in range(rowEnd-1, rowStart-1, -1):
        res.append(matrix[l][colStart])
    colStart += 1

  return res

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s