Baozi Leetcode solution 59: Sprial Matrix II

Problem Statement

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

Example:

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

Problem link

Video Tutorial

You can find the detailed video tutorial here

Youtube
B站

Thought Process

Straight forward question, could use Spiral Matrix exact same recursion algorithm to solve this, you can also watch that video tutorial here

Still needs pay attribute to this guy, had another great solution:

https://leetcode.com/problems/spiral-matrix-ii/discuss/22282/4-9-lines-Python-solutions

Solutions

 1 public int[][] generateMatrix(int n) {
 2     assert n >= 0;
 3
 4     int[][] res = new int[n][n];
 5
 6     this.generateMatrixHelper(0, 0, n, n, res, 1);
 7     return res;
 8 }
 9
10 private void generateMatrixHelper(
11         int i,
12         int j,
13         int rowSize,
14         int colSize,
15         int[][] matrix,
16         int num
17 ) {
18     if (rowSize <= 0 || colSize <= 0) {
19         return;
20     }
21
22     if (rowSize == 1 && colSize == 1) {
23         matrix[i][j] = num;
24         return;
25     }
26     if (rowSize == 1) {
27         for (int k = j; k < j + colSize; k++) {
28             matrix[i][k] = num;
29             num++;
30         }
31         return;
32     }
33
34     if (colSize == 1) {
35         for (int k = i; k < i + rowSize; k++) {
36             matrix[k][j] = num;
37             num++;
38         }
39         return;
40     }
41
42     // do the spiral
43     for (int k = j; k < j + colSize; k++) {
44         matrix[i][k] = num++;
45     }
46
47     for (int k = i + 1; k < i + rowSize; k++) {
48         matrix[k][j + colSize - 1] = num++;
49     }
50
51     for (int k = j + colSize - 2; k >= i; k--) {
52         matrix[i + rowSize - 1][k] = num++;
53     }
54
55     for (int k = i + rowSize - 2; k > i; k--) {   // both the start and end need to be i, j, and also care about length
56         matrix[k][j] = num++;
57     }
58
59     this.generateMatrixHelper(i + 1, j + 1, rowSize - 2, colSize - 2, matrix, num);
60 }

Simulation using Recursion

Time Complexity: O(M*N) where M, N is row and col of matrix

Space Complexity: O(M*N) since we used list to store the result, where M, N is row and col of matrix

References

Spiral Matrix