59

59. Spiral Matrix II (Medium)

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

 

Example 1:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

Example 2:

Input: n = 1
Output: [[1]]

 

Constraints:

• 1 <= n <= 20

Companies:
tiktok, Apple, Amazon

Related Topics:
Array, Matrix, Simulation

Similar Questions:

• Spiral Matrix (Medium)
• Spiral Matrix III (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/spiral-matrix-ii/
// Author: github.com/lzl124631x
// 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;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/spiral-matrix-ii/
// Author: github.com/lzl124631x
// 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));
        int i = 0, j = 0, d = 0, dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
        for (int val = 1; val <= n * n; ++val) {
            ans[i][j] = val;
            int x = i + dirs[d][0], y = j + dirs[d][1];
            if (x < 0 || x >= n || y < 0 || y >= n || ans[x][y]) d = (d + 1) % 4;
            i += dirs[d][0];
            j += dirs[d][1];
        }
        return ans;
    }
};