4
\$\begingroup\$

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]
\$\endgroup\$
2
+50
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ great. Thank you. \$\endgroup\$ – NinjaG Feb 4 at 6:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.