Spiral Matrix II

1. Initialize an n x n matrix, matrix, with zeros.
2. Initialize row = 0, col = 0.
3. Define an array of directions dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}} for Right, Down, Left, Up.
4. Initialize a direction index dirIndex = 0.
5. Loop with a counter val from 1 to n*n: a. Place the current value: matrix[row][col] = val. b. Calculate the coordinates of the next cell in the current direction: nextRow, nextCol. c. Check if (nextRow, nextCol) is out of bounds or has already been filled (i.e., matrix[nextRow][nextCol] != 0). d. If the next cell is invalid, update the direction: dirIndex = (dirIndex + 1) % 4. e. Update row and col for the next iteration based on the current dirIndex.
6. Return the filled matrix.

We can implement this by maintaining the current coordinates (row, col) and a direction index. An array of directions, e.g., {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, can represent the four movements (Right, Down, Left, Up).

The process starts at (0, 0) with the initial direction as Right. We loop from 1 to n*n, placing each number in the matrix. After placing a number, we check if the next step in the current direction is valid (i.e., within the matrix bounds and not already visited). If it's not valid, we update our direction to the next one in the sequence (e.g., from Right to Down). Then, we update our current (row, col) based on the (possibly new) direction to prepare for the next number.

1class Solution {2    public int[][] generateMatrix(int n) {3        int[][] matrix = new int[n][n];4        if (n == 0) {5            return matrix;6        }7        8        int row = 0, col = 0;9        // Directions: 0: Right, 1: Down, 2: Left, 3: Up10        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};11        int dirIndex = 0;12        13        for (int val = 1; val <= n * n; val++) {14            matrix[row][col] = val;15            16            // Calculate the next potential position17            int nextRow = row + dirs[dirIndex][0];18            int nextCol = col + dirs[dirIndex][1];19            20            // Check if the next position is invalid (out of bounds or already filled)21            if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= n || matrix[nextRow][nextCol] != 0) {22                // If invalid, change direction (turn 90 degrees clockwise)23                dirIndex = (dirIndex + 1) % 4;24            }25            26            // Update position for the next number to be placed27            // This update is skipped for the very last number to avoid out-of-bounds access.28            if (val < n * n) {29                row += dirs[dirIndex][0];30                col += dirs[dirIndex][1];31            }32        }33        return matrix;34    }35}

1. Create an n x n matrix, matrix.
2. Initialize a counter num = 1.
3. Initialize four boundary pointers: top = 0, bottom = n - 1, left = 0, right = n - 1.
4. Loop as long as top <= bottom and left <= right: a. Fill top row: Iterate from left to right, setting matrix[top][i] = num++. b. Increment top. c. Fill right column: Iterate from top to bottom, setting matrix[i][right] = num++. d. Decrement right. e. Fill bottom row: If top <= bottom, iterate from right down to left, setting matrix[bottom][i] = num++. f. Decrement bottom. g. Fill left column: If left <= right, iterate from bottom down to top, setting matrix[i][left] = num++. h. Increment left.
5. Return the filled matrix.

We start with the boundaries representing the entire matrix: top = 0, bottom = n - 1, left = 0, right = n - 1. A counter num starts at 1.

The process is contained within a while loop that runs as long as left <= right and top <= bottom. Inside the loop, we perform four distinct steps to fill one layer:

1. Fill Top Row: Traverse from left to right and fill matrix[top][i]. Then, move the top boundary down (top++).
2. Fill Right Column: Traverse from top to bottom and fill matrix[i][right]. Then, move the right boundary left (right--).
3. Fill Bottom Row: Traverse from right to left and fill matrix[bottom][i]. Then, move the bottom boundary up (bottom--).
4. Fill Left Column: Traverse from bottom to top and fill matrix[i][left]. Then, move the left boundary right (left++).

Conditional checks (if (top <= bottom) and if (left <= right)) are needed before filling the bottom row and left column to correctly handle matrices where n is odd, which results in a single central element or a single row/column in the center.

1class Solution {2    public int[][] generateMatrix(int n) {3        int[][] matrix = new int[n][n];4        if (n == 0) {5            return matrix;6        }7        8        int top = 0, bottom = n - 1;9        int left = 0, right = n - 1;10        int num = 1;11        12        while (top <= bottom && left <= right) {13            // Traverse Right (fill top row)14            for (int i = left; i <= right; i++) {15                matrix[top][i] = num++;16            }17            top++;18            19            // Traverse Down (fill right column)20            for (int i = top; i <= bottom; i++) {21                matrix[i][right] = num++;22            }23            right--;24            25            // Traverse Left (fill bottom row)26            if (top <= bottom) { // Check if there's still a valid row to fill27                for (int i = right; i >= left; i--) {28                    matrix[bottom][i] = num++;29                }30                bottom--;31            }32            33            // Traverse Up (fill left column)34            if (left <= right) { // Check if there's still a valid column to fill35                for (int i = bottom; i >= top; i--) {36                    matrix[i][left] = num++;37                }38                left++;39            }40        }41        42        return matrix;43    }44}