Copy a Spiral Matrix
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. - Returns the the 1D array.
For example:
input: 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. 2]
What pattern(s) jump out at you when looking at the above image of a spiral clockwise matrix?
If you are tempted to change the matrix - don't. There's no need to do this.
Have you checked for negative or out of bounds indices?
Double check that each value is copied only once!
Let inputMatrix be a matrix of numRows rows and numCols columns.
Look carefully at the image above. Instead of following numerical order, we'll copy the outer edges of the array, in order. Then we'll move on to the inner edges. These edges create the spiral. Copy the edges in in the following order:
- Top row from left to right.
- Rightmost column from top to bottom.
- Bottom row from right to left.
- Leftmost column from bottom to top.
We'll need to keep track of our edges in order to figure which row/column is next. To do that, we'll maintain 4 indices:
topRow- index of the the uppermost row to be copied, starting from0and incrementing.btmRow- index of the the lowermost row to be copied, starting fromnumRows-1and decrementing.leftCol- index of the leftmost column to be copied, starting from0and incrementing.rightCol- index of the the rightmost column to be copied, starting fromnumCols-1and decrementing.
Pseudocode:
function spiralCopy(inputMatrix): numRows = inputMatrix.length numCols = inputMatrix[0].length topRow = 0 btmRow = numRows - 1 leftCol = 0 rightCol = numCols - 1 result = [] while (topRow <= btmRow AND leftCol <= rightCol): # copy the next top row for i from leftCol to rightCol: result.push(inputMatrix[topRow][i]) topRow++ # copy the next right hand side column for i from topRow to btmRow: result.push(inputMatrix[i][rightCol]) rightCol-- # copy the next bottom row if (topRow <= btmRow): for i from rightCol to leftCol: result.push(inputMatri[btmRow][i]) btmRow-- # copy the next left hand side column if (leftCol <= rightCol): for i from btmRow to topRow: result.push(inputMatrix[i][leftCol]) leftCol++ return result
It's easy to create off-by-one errors when implementing this solution, so be sure to run through your solution with an example input.
Time Complexity: Iterating over N∙M cells, where N is the number of rows and M the number of columns, and copying them into any array takes O(N∙M). Note that this is a linear time complexity since the size of the input is O(N∙M).
Space Complexity: We used an auxiliary array of size N∙M as a return value, hence the space complexity is O(N∙M). This is a linear space complexity since the size of the input is O(N∙M) as well.
def spiral_copy(inputMatrix):
numRows = len(inputMatrix)
numCols = len(inputMatrix[0]) if numRows > 0 else 0
topRow = 0
btmRow = numRows - 1
leftCol = 0
rightCol = numCols - 1
result = []
while topRow <= btmRow and leftCol <= rightCol:
# Copy the next top row
for i in range(leftCol, rightCol + 1):
result.append(inputMatrix[topRow][i])
topRow += 1
# Copy the next right hand side column
for i in range(topRow, btmRow + 1):
result.append(inputMatrix[i][rightCol])
rightCol -= 1
# Copy the next bottom row
if topRow <= btmRow:
for i in range(rightCol, leftCol - 1, -1):
result.append(inputMatrix[btmRow][i])
btmRow -= 1
# Copy the next left hand side column
if leftCol <= rightCol:
for i in range(btmRow, topRow - 1, -1):
result.append(inputMatrix[i][leftCol])
leftCol += 1
return result
import Foundation func spiralCopy(inputMatrix: [[Int]]) -> [Int] { let arr = inputMatrix var top = 0, down = arr.count - 1 var left = 0, right = arr[0].count - 1 if top == down && left == right { return arr[top] } var ans: [Int] = [] while top <= down && left <= right { for i in left..<right { ans.append(arr[top][i]) } for i in top..<down { ans.append(arr[i][right]) } for i in stride(from: right, to: left, by: -1) { ans.append(arr[down][i]) } for i in stride(from: down, to: top, by: -1) { ans.append(arr[i][top]) } top += 1 left += 1 right -= 1 down -= 1 } return ans }