Copy a Spiral Matrix

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 from 0 and incrementing.
• btmRow - index of the the lowermost row to be copied, starting from numRows-1 and decrementing.
• leftCol - index of the leftmost column to be copied, starting from 0 and incrementing.
• rightCol - index of the the rightmost column to be copied, starting from numCols-1 and 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.