Matrix Spiral Copy

Description

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 1:

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]

See the illustration below to understand better what a clockwise spiral order looks like.

Constraints:

• [time limit] 5000ms
• [input] array.array.integer inputMatrix
  • 1 ≤ inputMatrix[0].length ≤ 100
  • 1 ≤ inputMatrix.length ≤ 100
• [output] array.integer

---

Solutions

Solution 1

Intuition

Let inputMatrix be a matrix of numRows rows and numCols columns.

The general idea of the solution is to copy the 4 edges of the spiral rim we currently at and then move on to copy the next (inner) rim. We keep doing that until we reached to the end of the spiral. We copy edges in the following order:

• Copy the uppermost row from left to right.
• Copy the rightmost column from top to bottom.
• Copy the lowermost row from right to left.
• Copy the leftmost column from bottom to top.

In order to figure what is the next row/column to copy in the spiral order we 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.

Code

static int[] spiralCopy(int[][] inputMatrix) {

    // your code goes here
    int rows = inputMatrix.length;
    int columns = inputMatrix[0].length;

    int startRow = 0, endRow = rows - 1;
    int startColumn = 0, endColumn = columns - 1;
    int index = 0;
    int n = rows * columns;
    int[] ans = new int[n];
    while (index < n) {
        for (int i = startColumn; i <= endColumn && index < n; i++) {
            ans[index++] = inputMatrix[startRow][i];
        }
        startRow++;
        for (int i = startRow; i <= endRow && index < n; i++) {
            ans[index++] = inputMatrix[i][endColumn];
        }
        endColumn--;
        for (int i = endColumn; i >= startColumn && index < n; i--) {
            ans[index++] = inputMatrix[endRow][i];
        }
        endRow--;
        for (int i = endRow; i >= startRow && index < n; i--) {
            ans[index++] = inputMatrix[i][startColumn];
        }
        startColumn++;
    }

    return ans;
}

Complexity

• 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.

---

Solution 2

Intuition

Code

Complexity

• Time:
• Space:

---

Similar Questions