Clockwise spiral traversal of 2D input matrix I found this interview question online at Pramp:


  Given a 2D array (matrix) inputMatrix of integers, create a function spiralCopy that copies inputMatrix’s values into a 1D array in a spiral order, clockwise. Your function then should return that array. Analyze the time and space complexities of your solution.
  
  Example:

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

  
  output:

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

  
  Constraints:
  
  
  1 ≤ inputMatrix[0].length ≤ 100
  1 ≤ inputMatrix.length ≤ 100
  


My solution

def spiral_copy(inputMatrix):
    output = []

    top_row = 0
    bottom_row = len(inputMatrix) - 1
    left_col = 0
    right_col = len(inputMatrix[0]) - 1

    while top_row &lt;= bottom_row and left_col &lt;= right_col:

        for i in range(left_col, right_col + 1):
            output.append(inputMatrix[top_row][i])
        top_row += 1

        for i in range(top_row, bottom_row + 1):
            output.append(inputMatrix[i][right_col])
        right_col -= 1

        if top_row &gt; bottom_row: break

        for i in range(right_col, left_col - 1, -1):
            output.append(inputMatrix[bottom_row][i])
        bottom_row -= 1 

        if left_col &gt; right_col: break

        for i in range(bottom_row, top_row - 1, -1):
            output.append(inputMatrix[i][left_col])
        left_col += 1  

    return output



Passed these 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]
You’re being a bit verbose, adding elements one at a time in a loop to the output array.  You can use .extend() to add several elements at once, and use a slice to extract the required elements from the inputMatrix rows:

output.extend( inputMatrix[top_row][left_col:right_col+1] )


Unfortunately, you can’t slice a column (without using numpy), but you can still use list comprehension:

output.extend( inputMatrix[row][right_col] for row in range(top_row, bottom_row+1) )


Adding the elements at the bottom of the spiral would require a slice using a negative step, but left_col-1 will initially evaluate to -1 so inputMatrix[bottom_row][right_col:left_col-1:-1] doesn’t work as desired.  You’d need to special case left_col == 0 and use the slice [right_col:None:-1] or [right_col::-1].  Alternately, you could use list comprehension.

Going up the left side is exactly like going down the right side: use list comprehension.

output.extend( inputMatrix[row][left_col] for row in range(bottom_row, top_row-1, -1) )




Notice I used row, instead of i, as the loop index.  I feel this makes the code a little clearer.



An alternative method of doing the spiral copy would be to separate the index generation from the copy.

output = [ inputMatrix[r][c] for r, c in spiral(len(inputMaxtrix), len(inputMatrix[0])) ]


where spiral(rows, cols) is a generator function for the spiral coordinates.  Writing the spiral generator left as an exercise to the student.