Spiral Matrix

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].

(Java Code on Github at the bottom of the post. )

My thoughts and solutions:

I saw a similar problem before about rotating a matrix clockwise for 90 degrees. The standard answer solved it by treating a matrix as several layers of items and process them from the outer layer to the inner layer (I solved it in a different way though). Now I think we can still use this idea here.

What do we mean by layer? For the example above, we have 2 layers.

  • Layer-0 contains 1,2 | 3, 6 | 9, 8 | 7, 4.
  • Layer -1 contains only one item 5.

Let’s try a few more examples:

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

In this example, it is a 5 by 4 matrix with 2 layers.

  • Layer-0 has 1,2,3 | 4,8,12,16|20,19,18|17,13,9,7.
  • Layer-1 has 5|6,11|15|14,10.

Another example with 3 layers

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

Two things we can generalize from these examples:

  •  for a M by N matrix, the number of layers can be calculated by:
int smaller = (M < N) ? M : N;
int nLayers = smaller % 2 == 0 ? (smaller/2) : (smaller/2) + 1;
  • For each layer, we have to go from left to right, top to bottom, right to left and bottom to top. And on different layers, these traverses start and end at different locations but there are rules we can follow. Try out a few examples on different layers and find out that rule: on layer L, we go left to right from matrix[?][?] to matrix[?][?] and we go top to bottom from matrxi[?][?] to matrix[?][?] …

Some corner cases we need to consider:

  • when the matrix is empty
  • a matrix like this [[1,2,3,4,5]]
  • a matrix like this [[1], [2], [3], [4], [5]]
  • a matrix like this [[1]]

So in the actual code, we need something to tell us if we are dealing with a one-column or one-row matrix.

  • one-column matrix: startLeft == startRight (going from left to right and vice versa is starting at the same location since there is only one column)
  • one-row matrix: startTop == startBottom (going from top to bottom and vice versa is starting at the same location since there is only one row)

Summary:

  • we can start with normal cases and write pseudo code of it
  • but before writing any actual code, think about the corner cases and we may need to change the pseudo code.

Code on github:

Enhanced by Zemanta
Advertisements
Spiral Matrix

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