Question

Formatted question description: https://leetcode.ca/all/59.html

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

@tag-array

Algorithm

Given that the rectangle is a square, we use n / 2 to calculate the number of rings. If n is an odd number, the middle point is not counted in the number of rings, so it needs to be assigned separately in the end, or the problem of subscript conversion Is difficult.

Code

Java

public class Spiral_Matrix_II {

	// @note: compare: very similar to rotate image one, layer by layer, each layer: length-2
	public class Solution_by_layer {
	    public int[][] generateMatrix(int n) {
	        if (n < 0) {
	            return null;
	        }

	        int[][] result = new int[n][n];

	        int xStart = 0;
	        int yStart = 0;
	        int num = 1;

	        while (n > 0) {
	            if (n == 1) { // if n is even, then no single center point
	                result[yStart][xStart] = num++;
	                break;
	            }

	            for (int i = 0; i < n - 1; i++) {
	                result[yStart][xStart + i] = num++;
	            }

	            for (int i = 0; i < n - 1; i++) {
	                result[yStart + i][xStart + n - 1] = num++;
	            }

	            for (int i = 0; i < n - 1; i++) {
	                result[yStart + n - 1][xStart + n - 1 - i] = num++;
	            }

	            for (int i = 0; i < n - 1; i++) {
	                result[yStart + n - 1 - i][xStart] = num++;
	            }

	            xStart++;
	            yStart++;
	            n = n - 2;
	        }

	        return result;
	    }
	}


    public class Solution {

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

            int[][] result = new int[n][n];

            if (n <= 0) {
                return result;
            }

            int i = 0, j = 0; // initiate row and column

            int leftBoundary = 0, upBoundary = 1;
            int rightBoundary = n - 1, downBoundary = n - 1; // marking boundary index

            /*
                direction: 1 is up, 2 is down, 3 is left, 4 is right
            */

            // at beginning direction is right;
            int direction = 4;

            for (int num = 1; num <= n * n; num++) {

                result[i][j] = num;

                // switch case
                if (direction == 1) { // move right

                    if (i == upBoundary) {
                        direction = 4;
                        j++;

                        upBoundary++;

                    } else {
                        i--;
                    }
                }

                else if (direction == 2) {

                    if (i == downBoundary) {
                        direction = 3;
                        j--;

                        // update boundary
                        downBoundary--;
                    } else {
                        i++;
                    }
                }

                else if (direction == 3) {

                    if (j == leftBoundary) {
                        direction = 1;
                        i--;

                        // update boundary
                        leftBoundary++;

                    } else {
                        j--;
                    }
                }

                else { // direction == 4

                    // check boundary
                    if (j == rightBoundary) {
                        direction = 2;
                        i++;

                        // row boundary is 1 less now
                        rightBoundary--;
                    } else {
                        j++;
                    }

                }
            }

            return result;

        }
    }

}

// OJ: https://leetcode.com/problems/spiral-matrix-ii/
// Time: O(N^2)
// Space: O(1) extra space
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n));
        for (int i = 0, d = 1; i < n / 2; ++i) {
            int len = n - 2 * i - 1;
            for (int j = 0; j < len; ++j) ans[i][i + j] = d++;
            for (int j = 0; j < len; ++j) ans[i + j][n - i - 1] = d++;
            for (int j = 0; j < len; ++j) ans[n - i - 1][n - i - j - 1] = d++;
            for (int j = 0; j < len; ++j) ans[n - i - j - 1][i] = d++;
        }
        if (n % 2) ans[n / 2][n / 2] = n * n;
        return ans;
    }
};

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        ans = [[0] * n for _ in range(n)]
        dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
        i = j = k = 0
        for v in range(1, n * n + 1):
            ans[i][j] = v
            x, y = i + dirs[k][0], j + dirs[k][1]
            if x < 0 or y < 0 or x >= n or y >= n or ans[x][y]:
                k = (k + 1) % 4
                x, y = i + dirs[k][0], j + dirs[k][1]
            i, j = x, y
        return ans

############

class Solution(object):
  def generateMatrix(self, n):
    """
    :type n: int
    :rtype: List[List[int]]
    """
    ans = [[0] * n for _ in range(n)]
    left, right, up, down = 0, n - 1, 0, n - 1
    k = 1
    while left <= right and up <= down:
      for i in range(left, right + 1):
        ans[up][i] = k
        k += 1
      up += 1
      for i in range(up, down + 1):
        ans[i][right] = k
        k += 1
      right -= 1
      for i in reversed(range(left, right + 1)):
        ans[down][i] = k
        k += 1
      down -= 1
      for i in reversed(range(up, down + 1)):
        ans[i][left] = k
        k += 1
      left += 1
    return ans

59 - Spiral Matrix II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions