Algorithm Problem 002: Spiral Matrix II

Problem

Problem Source：59. Spiral Matrix II

Problem Description：

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 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

Approach

This problem is a typical simulation problem where we need to traverse the entire matrix as described.

Approach 1

My approach is to divide the matrix into layers and traverse each layer one by one. For example, when $n = 3$, the matrix is:

Here, we define the first layer as layer = 0, which contains numbers 1 to 8. The second layer is layer = 1, containing the number 9.

While traversing each layer, write the loop codes for moving right (1, 2), moving down (3, 4), moving left (5, 6), and moving up (7, 8).

The key to this approach is to find the mathematical pattern for the relationship between layer and the length of the current row/column being traversed.

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        int counter = 1;

        for (int layer = 0; layer <= n / 2; layer++) {
            // Move right
            for (int j = layer; j < n - layer - 1; ++j, ++counter) {
                ans[layer][j] = counter;
            }
            // Move down
            for (int i = layer; i < n - layer - 1; ++i, ++counter) {
                ans[i][n - layer - 1] = counter;
            }
            // Move left
            for (int j = n - layer - 1; j > layer; --j, ++counter) {
                ans[n - layer - 1][j] = counter;
            }
            // Move up
            for (int i = n - layer - 1; i > layer; --i, ++counter) {
                ans[i][layer] = counter;
            }
        }
        // For square matrices with odd length, manually handle the center element
        if (n % 2 == 1) {
            ans[n / 2][n / 2] = counter;
        }

        return ans;
    }
}

Clearly, this approach is error-prone as finding the pattern is tedious.

Some experts on LeetCode provide an alternative solution that avoids finding the pattern, such as Krahets’s solution：manually control the four boundaries (up, down, left, right), and when reaching a boundary, turn to the next direction.

Approach 2

Since we are dealing with a matrix (a regular shape), we tend to control the traversal from a macro perspective, as in Approach 1. Macro means understanding the global picture, as seen in my approach of finding mathematical patterns and the experts’ approach of controlling the four boundaries.

Now, let’s approach the problem from a micro perspective: what if we stand on a huge chessboard with invisible boundaries and need to fill in these numbers, how would we do it? We can only see the numbers on the surrounding squares. At this point, the macro approach is no longer effective, so what should we do?

Suppose we stand on square 1 (facing right) and move forward, filling in the numbers along the path. When we reach square 3, we find that there is no way forward. Since we want to fill in the numbers clockwise, let’s turn right (facing down), and now the square we are facing is where we should fill in the number 4.

Similarly, when we reach square 8 (facing up), the squares in front have already been filled with number 1. Let’s turn right again (facing right), and now the square we are facing is where we should fill in the number 9.

Therefore, in the code, let’s focus only on the current coordinates of the agent and make it keep moving in one direction until it reaches a boundary or the square has already been filled with a number. When this happens, we turn right.

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        // (dx[k], dy[k]) represents the direction to move, in the order of right, down, left, up, right ...
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        // (x, y) is the agent's coordinates;
        // dir represents the current direction to move, it is the index of the dx, dy arrays
        int x = 0, y = 0, dir = 0;
        // Loop variables, and the condition for the loop to exit
        int counter = 1, limit = n * n;
        while (counter <= limit) {
            // Current coordinates are within the boundaries, and the current square is not filled with a number
            while (0 <= x && x < n && 0 <= y && y < n && ans[x][y] == 0) {
                ans[x][y] = counter;
                counter++;
                // keep moving
                x += dx[dir];
                y += dy[dir];
            }
            // Step back one square
            x -= dx[dir];
            y -= dy[dir];
            // Turn right
            dir = (dir + 1) % dx.length;
            // After moving forward one step, the position (x, y) is the first square to be processed in the next while loop
            x += dx[dir];
            y += dy[dir];
        }
        return ans;
    }
}

Reflection

I came up with Approach 2 because I recently solved a problem that required filling numbers clockwise in an isosceles right-angled triangle (with the right angle parallel to the coordinate axes).

For example, when n = 4, we need to fill in the numbers as follows:

For the macro approach that finds patterns from a high-level perspective, I really didn’t bother and found it cumbersome.

With Approach 2, the so-called clockwise filling is essentially cycling through these directions: up, down-right, left. So, at the code level:

int[] dx = {-1, 1, 0};
int[] dy = {0, 1, -1};

A slight modification to the code for Approach 2 is all that is needed.