Clockwise spiral traversal of 2D input matrix

Question

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 <= bottom_row and left_col <= 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 > 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 > 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]

Answer 1

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.