Question

LeetCode Link | 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.

Constrains

  • 1 <= n <= 20

Example

Example 1

Example 1

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

Example 2

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

Solution Approach

Method: Manual / Simulate

Constrains

  • None

This method does not have any limitations.

Concept Explanation

This problem often appears in interviews. It does not involve any specific algorithms, but rather simulates a process, which greatly tests the control over the code.

To solve this problem, it is necessary to adhere to the principle of loop invariants. To simulate the process of drawing a matrix clockwis, it has following type of action:

  • Fill the top row from left to right. (Right)
  • Fill the right column from top to bottom. (Down)
  • Fill the bottom row from right to left. (Left)
  • Fill the left column from bottom to top. (Up)

Continue this way from the outside inward, circle by circle. In one complete round here, we need to draw each of the four edges. To draw these four edges should adhere to a consistent principle of either left-closed and right-open, or left-open and right-closed, so that the entire round can be drawn according to a unified rule.

Now, following the principle of left-closed and right-open, it should be like this:

Filling Chunk in four edges

Each color represents an edge, and the length we traverse can reveal the rules for handling each corner. At the corners, we give way to a new edge to continue drawing. This also adheres to the principle of left-closed and right-open for each edge.

Code

  • Time complexity: O(n2)
  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
function generateMatrix(n: number): number[][] {
	// Array Filler with empty elements
	let result = Array.from({ length: n }, () => new Array(n));

	let startX = 0, startY = 0;         // chunk start coordinate
	let x: number, y: number;           // coordinate to fill
	let value = 1;                      // value to fill

	/*
	 * To fill number in spiral, it needs to fill in cycle.
	 * One set of right, down, left, up are called in one cycle.
	 * If cycleNum is 0, it means no more cycle need to fill.
	 */
	let cycleNum = Math.floor(n/2);   // Cycles in matrix
	let chunkNum = n - 1;            // number of tiles in one chunk

	// Start to fill
	while (cycleNum--) {
		// Update start coordinate of the chunk
		x = startX; y = startY;

		// Right Direction Chunk
		while (x < startX + chunkNum) {
			result[y][x++] = value++;
		}
		// Down Direction Chunk
		while (y < startY + chunkNum) {
			result[y++][x] = value++;
		}
		// Left Direction Chunk
		while (x > startX) {
			result[y][x--] = value++;
		}
		// Up Direction Chunk
		while (y > startY) {
			result[y--][x] = value++;
		}
		// Update start coordinate of next circle
		startX++; startY++;
		// Update Chunk Size
		chunkNum -= 2;
	}

	// Center Left (only odd number)
	if ( n % 2 == 1) result[startX][startY] = value;

	return result;
};

Conclusion

When dealing with problems that do not involve specific algorithms and are purely about simulating processes, but still greatly test your control over the code, you should not rush to write the code immediately. Instead, you should first break down the process into multiple fixed-format and repetitive segments, then implement them one by one, ultimately achieving a well-organized and logical structure in the entire code.