Interview Questions

Print a matrix in spiral order
The input for this problem will be a matrix, or multidimensional array, which will be represented by N arrays each of N length, and your goal is to print the matrix in a spiral order. For example, if the input is:
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
then this matrix should be printed out in a list like so:
[1, 2, 3, 6, 9, 8, 7, 4, 5]
The spiral begins at the top left of the matrix and loops around it towards the center in a clockwise pattern. Below is a clever algorithm that uses recursion to print a matrix in spiral order:

Algorithm

(1) Every other iteration through the matrix peel off the first row and last column of the matrix. So for the above array we should get: [[1, 2, 3], [6, 9]]. Store these elements in a list and then pass the modified matrix to another function. The modified matrix currently looks like this:
[[4, 5], [7, 8]]
(2) Now peel off the last row and first column from the matrix, reverse each one, and add them to the previous list. Our spiral list should look like the following so far: [[1, 2, 3], [6, 9], [8, 7], [4]]. (3) Now continue from step 1 until the matrix has no elements left and return the final spiraled list.

Code

```function layerTopRight(matrix) {

// remove and store the first row from matrix
var top = matrix.splice(0, 1);

// store the right column of the matrix
var right = [];

// remove the last column from the matrix
for (var i = 0; i < matrix.length; i++) {
var e = matrix[i].splice(-1, 1);
right.push(e);
}

// return the top row and last column elements as a list

}

function layerBottomLeft(matrix) {

// remove and store the last row from matrix in reverse order
var bottom = matrix.splice(matrix.length-1, 1)[0].reverse();

// store the left column of the matrix
var left = [];

// remove the first column from the matrix
for (var i = 0; i < matrix.length; i++) {
var e = matrix[i].splice(0, 1);
left.push(e);
}

// return the top row and last column elements as a list
return bottom.concat(left.reverse()).toString().split();

}

// our main spiral function that will
// return a final spiral ordered list
function spiral(matrix) {

// where we store our final spiraled list
var spir = [];

while (matrix.length > 0) {

// if only 1 more element left in matrix
if (matrix.length === 1) {
spir.push(matrix[0]);
break;
}

// return the spiraled list of the top row and
// right column for this matrix
var tr = layerTopRight(matrix);
spir.push(tr);

// return the spiraled list of the bottom row and
// left column for this matrix
var bl = layerBottomLeft(matrix);
spir.push(bl);

}

return spir.toString().split();

}

// setup a matrix
var M = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]];

// return it in spiral order
spiral(M);
```
```def layerTopRight(matrix):

# remove and store the first row from matrix
top = matrix.pop(0)

# store the right column of the matrix
right = []

# remove the last column from the matrix
for i in range(0, len(matrix)):
e = matrix[i].pop()
right.append(e)

# return the top row and last column elements as a list

def layerBottomLeft(matrix):

# remove and store the last row from matrix in reverse order
bottom = matrix.pop()[::-1]

# store the left column of the matrix
left = []

# remove the first column from the matrix
for i in range(0, len(matrix)):
e = matrix[i].pop(0)
left.append(e)

# return the top row and last column elements as a list
return bottom + left[::-1]

# our main spiral function that will
# return a final spiral ordered list
def spiral(matrix):

# where we store our final spiraled list
spir = []

while len(matrix) > 0:

# if only 1 more element left in matrix
if len(matrix) == 1:
spir += matrix[0]
break

# return the spiraled list of the top row and
# right column for this matrix
tr = layerTopRight(matrix)
spir += tr

# return the spiraled list of the bottom row and
# left column for this matrix
bl = layerBottomLeft(matrix)
spir += bl

return spir

# setup a matrix
M = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]

# return it in spiral order
print spiral(M)
```

Running time

This algorithm runs in O(n2) time, where n represents an n x n matrix, because it needs to loop through the entire matrix at least once to reach every single element. Reversing the bottom row and left column of the matrix on every other iteration adds to the running time, but a fast array reverse algorithm can run in O(n).

Sources

http://www.careercup.com/question?id=2991909
mrdaniel published this on 11/12/15 |
• +
• 5
• -
• I tried this way......... ``` function spiral(matrix){ var list= []; while(matrix.length>1){ //Right list= list.concat(matrix.splice(0,1)[0]); //Down for(var idx in matrix){ list.push(matrix[idx].splice(-1)[0]); } //Left list= list.concat(matrix.splice(-1,1)[0].reverse()); //Up for(var idx=matrix.length-1;idx>=0;idx--){ list.push(matrix[idx].splice(0,1)[0]); } } if(matrix.length>0){ list.push(matrix.pop()[0]); } return list; } // setup a matrix var M = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]; // return it in spiral order spiral(M); ```
• +
• 0
• -
• ``` def print_spiral_order(mat): """ Prints a matrix represented as a list of lists in spiral order Args: mat: list of lists Returns: matrix printed in spiral order. """ while mat: for x in mat.pop(0): print(x) for v in mat: print(v.pop()) if mat: for x in mat.pop()[::-1]: print(x) for v in mat[::-1]: print(v.pop(0)) ```
• +
• 0
• -
• You don't need to slice and dice the matrix, neither do you need to reverse anything. Here's a Scala implementation that uses simple recursion. It can be trivially converted to a Python implementation. ``` def matrixSpiral(xs: IndexedSeq[IndexedSeq[Int]]): Seq[Int] = { val rows = xs.size val cols = xs.headOption.map(_.size).getOrElse(0) def loop(row: Int, col: Int): Seq[Int] = { val lastRow = rows - row - 1 val lastCol = cols - col - 1 if (row > lastRow || col > lastCol) Seq.empty[Int] else { val ys = // top (col to lastCol) .map(c => xs(row)(c)) ++ // right; since top loop already included the top right element, exclude it; also exclude bottom right // element because it's included in the bottom loop (row + 1 until lastRow) .map(r => xs(r)(lastCol)) ++ // bottom ( if (row < lastRow) (lastCol to col by -1).map(c => xs(lastRow)(c)) else Seq.empty[Int] ) ++ // left; exclude bottom left and top left elements ( if (col < lastCol) (lastRow - 1 until row by -1).map(r => xs(r)(col)) else Seq.empty[Int] ) ys ++ loop(row + 1, col + 1) } } loop(0, 0) } ```
• +
• -2
• -
• ``` def spiral(matrix): spiral_array=[] for row in range(len(matrix)): if row%2==0: spiral_array.extend(matrix[row]) else: matrix[row].reverse() spiral_array.extend(matrix[row]) return spiral_array ```