LeetCode 59 - Spiral Matrix II

Given an integer $n$ , generate a square matrix filled with elements from 1 to $n^2$  in spiral order

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

public int[][] generateMatrix(int n) {

        if (n < 0)

            return null;

        int[][] matrix = new int[n][n];

        int startRow = 0, startColumn = 0;

        int endRow = n-1, endColumn = n-1;

        int num = 1;

        // Work on 2-D submatrix ranging from Row startRow to endRow,

        // Column startColumn to endColumn

        while (startRow < endRow && startColumn < endColumn) {

            // Top edge, left-to-right

            for (int k = startColumn; k < endColumn; k++)

                matrix[startRow][k] = num++;

            // Right edge, top-to-bottom

            for (int k = startRow; k < endRow; k++)

                matrix[k][endColumn] = num++;

            // Bottom edge, right-to-left

            for (int k = endColumn; k > startColumn; k--)

                matrix[endRow][k] = num++;

            // Left edge, bottom-to-top

            for (int k = endRow; k > startRow; k--)

                matrix[k][startColumn] = num++;

            // Prepare to work on its nested submatrix

            startRow++;

            startColumn++;

            endRow--;

            endColumn--;

        }

        // When n is odd, there is still one cell at the center of the matrix

        // that has not been assigned a value

        if ((n & 1) == 1)

            matrix[startRow][startColumn] = num;

        return matrix;

    }

这个题目跟LeetCode[Array]: Spiral Matrix不同的是：这个题目并不适合用递归，因为vector<vector<int> >不好递归生成。

https://leetcode.com/problems/spiral-matrix-ii/discuss/22292/Share-my-java-solution
https://leetcode.com/problems/spiral-matrix-ii/discuss/22295/Java-simple-and-clear-easy-understood

        while(left<=right && top <=bottom){

public static int[][] generateMatrix(int n) {
 int[][] ret = new int[n][n];
 int left = 0,top = 0;
 int right = n -1,down = n - 1;
 int count = 1;
 while (left <= right) {
  for (int j = left; j <= right; j ++) {
   ret[top][j] = count++;
  }
  top ++;
  for (int i = top; i <= down; i ++) {
   ret[i][right] = count ++;
  }
  right --;
  for (int j = right; j >= left; j --) {//\\
   ret[down][j] = count ++;
  }
  down --;
  for (int i = down; i >= top; i --) {//\\
   ret[i][left] = count ++;
  }
  left ++;
 }
 return ret;
}

http://www.geeksforgeeks.org/print-a-given-matrix-in-spiral-form/

void spiralPrint(int m, int n, int a[R][C])

{

    int i, k = 0, l = 0;

    /*  k - starting row index

        m - ending row index

        l - starting column index

        n - ending column index

        i - iterator

    */

    while (k < m && l < n)

    {

        /* Print the first row from the remaining rows */

        for (i = l; i < n; ++i)

        {

            printf("%d ", a[k][i]);

        }

        k++;

        /* Print the last column from the remaining columns */

        for (i = k; i < m; ++i)

        {

            printf("%d ", a[i][n-1]);

        }

        n--;

        /* Print the last row from the remaining rows */

        if ( k < m)

        {

            for (i = n-1; i >= l; --i)

            {

                printf("%d ", a[m-1][i]);

            }

            m--;

        }

        /* Print the first column from the remaining columns */

        if (l < n)

        {

            for (i = m-1; i >= k; --i)

            {

                printf("%d ", a[i][l]);

            }

            l++;   

        }       

    }

}

X. https://leetcode.com/problems/spiral-matrix-ii/discuss/22473/Share-my-simple-solution-with-graphical-explanation-Java

If n is odd, only the first direction will cover it (top left -> right, shown as # in the graph), because the other three direction all start from the next position( +1 or -1).

  * -> -> ->
  * ^      |
  * |      |
  * <- <-- V
  * 
  * # # # #
  * %     $
  * %     $
  * & & & $
  *     
    public static int[][] generateMatrix(int n) {
     int[][] res = new int[n][n];
     
     int num = 1;
     int level = (int) Math.ceil(n / 2.);
     
     for(int i = 0; i < level; i++) {
      
      // top left -> right, shown as #
      for(int j = i; j < n - i; j++)
       res[i][j] = num++;
      
      // top right + 1 -> bot, shown as $
      for(int j = i + 1; j < n - i; j++)
       res[j][n - i - 1] = num++;
      
      // bot right - 1 -> left, shown as &
      for(int j = n - i - 2; j >= i; j--)
       res[n - i - 1][j] = num++;
      
      // bot left -1 -> top + 1, shown as %
      for(int j = n - i - 2; j > i; j--)
       res[j][i] = num++;
     }
     return res;
    }

http://www.geeksforgeeks.org/print-matrix-antispiral-form/

The idea is simple, we traverse matrix in spiral form and put all traversed elements in a stack. Finally one by one elements from stack and print them.

void antiSpiralTraversal(int m, int n, int a[R][C])

{

    int i, k = 0, l = 0;

    /*  k - starting row index

        m - ending row index

        l - starting column index

        n - ending column index

        i - iterator  */

    stack<int> stk;

    while (k <= m && l <= n)

    {

        /* Print the first row from the remaining rows */

        for (i = l; i <= n; ++i)

            stk.push(a[k][i]);

        k++;

        /* Print the last column from the remaining columns */

        for (i = k; i <= m; ++i)

            stk.push(a[i][n]);

        n--;

        /* Print the last row from the remaining rows */

        if ( k <= m)

        {

            for (i = n; i >= l; --i)

                stk.push(a[m][i]);

            m--;

        }

        /* Print the first column from the remaining columns */

        if (l <= n)

        {

            for (i = m; i >= k; --i)

                stk.push(a[i][l]);

            l++;

        }

    }

    while (!stk.empty())

    {

        cout << stk.top() << " ";

        stk.pop();

    }

}

Read full article from LeetCode - Spiral Matrix II | Darren's Blog