Find spiral 2D matrix (List of Lists) of ints in a clockwise spiral

Question

I got this question during my interview with Microsoft.

The question called 2D Snake. I'm wondering if my solution 1 passes the test, but if my solution 1 different from solution 2.

Let's have some fun with 2D Matrices! Write a method find_spiral to traverse a 2D matrix (List of Lists) of ints in a clockwise spiral order and append the elements to an output List of Integers.

Example:

Input Matrix:

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

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

Solution 1

def find_spiral(matrix):
 output = []
 while matrix:
 row = matrix.pop(0)
 output.extend(row)
 matrix = zip(*matrix)[::-1] 
 return output

Solution 2

def find_spiral(matrix): 
 spiral_list = []
 if matrix == None or len(matrix) == 0:
 return list
 m = len(matrix) 
 n = len(matrix[0])
 x=0
 y=0
 while(m>0 and n>0):
 if(m==1):
 i = 0
 while i < n:
 spiral_list.append(matrix[x][y])
 i += 1
 y += 1
 break
 elif(n==1):
 i = 0
 while i < m:
 spiral_list.append(matrix[x][y])
 i += 1
 x += 1
 break
 i = 0
 while i < n-1:
 spiral_list.append(matrix[x][y])
 i+=1
 y+=1
 j = 0
 while j < m-1:
 spiral_list.append(matrix[x][y])
 j+=1
 x+=1
 i = 0
 while i < n-1:
 spiral_list.append(matrix[x][y])
 i+=1
 y-=1
 j = 0
 while j < m-1:
 spiral_list.append(matrix[x][y])
 j+=1
 x-=1
 x+=1
 y+=1
 m=m-2
 n=n-2
 return spiral_list

Test cases:

Input 
[[1,2],[3,4]]
Expected Result
[1, 2, 4, 3]
Input
[[1,2],[3,4]
Expected Result
[1, 2, 4, 3]
Input
[[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Expected Result
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
input
[[1,2],[3,4]
Expected Result
[1, 2, 3, 4, 5, 6, 12, 18, 17, 16, 15, 14, 13, 7, 8, 9, 10, 11]
Input
[[1,0],[0,1]]
Expected Result
[1, 0, 1, 0]
Input
[[1,2,3],[4,5,6],[7,8,9]]
Expected Result
[1, 2, 3, 6, 9, 8, 7, 4, 5]

• Zeta: First code taken from github.com/tmantock/python/blob/master/snake.py,

Answer 1

Just reviewing solution 1.

1. The solution is clever (repeatedly extract the first row and rotate the remainder by a quarter-turn) and the code terse.

2. However, the code destructively modifies the input matrix by popping the first row. This would be surprising to the caller and might make it more difficult to use or to test.

3. The code does not work in Python 3: it fails with the exception:

   TypeError: 'zip' object is not subscriptable
   

   In Python 3 you would have to write list(zip(...)). Since Python 2.7 is close to its end of life it is a good idea to write code that would be easy to port to Python 3. In this case you could use

   from future_builtins import zip
   

   to get a version of the built-in zip function that's compatible with Python 3.

4. If the input is an \$n×ばつn\$ matrix, then rotating the remainder takes \$O(n^2)\$ and this has to be done \$O(n)\$ times, leading to a total runtime of \$O(n^3)\$. But intuitively it ought to be possible to output the spiral in \$O(n^2)\$.

   We can achieve this by implementing the same approach (repeatedly extract the first row and rotate the remainder by a quarter-turn) but instead of modifying the matrix, we instead modify our system of coordinates. This is probably easiest to see if I give the code first:

   def find_spiral_2(matrix):
    "Return list of elements of matrix in clockwise spiral order."
    h, w = len(matrix), len(matrix[0]) # Height and width of remainder
    i, j = 0, -1 # Current position in spiral
    di, dj = 0, 1 # Current direction of movement
    spiral = []
    while h > 0:
    # Output top row
    for _ in range(w):
    i += di
    j += dj
    spiral.append(matrix[i][j])
    # Remove top row and rotate quarter-turn
    h, w = w, h - 1
    di, dj = dj, -di
    return spiral
   

   The way this works is that we maintain the state of the algorithm in the form of the height \$h\$ and width \$w\$ of the remainder of the matrix, the coordinates \$(i, j)\$ of our current position along the spiral, and a vector \$(di, dj)\$ giving the current direction of movement along the spiral path.

   To output the top row, we follow the current direction for \$w\$ steps, leaving us in the top-right corner of (the remainder of) the matrix. Then, as in your solution, we remove the top row and rotate the remainder though a quarter-turn—or rather, we modify our coordinates to have this effect. Removing the top row subtracts 1 from \$h\$. Rotating the remainder through a quarter-turn causes \$w\$ and \$h\$ to swap (height becomes width and vice versa) and the current direction of movement to rotate through a quarter-turn. You should check that the line di, dj = dj, -di achieves this.

   It should be clear that this does not modify matrix, and runs in \$O(n^2)\$ as required.