Spiral Matrix II

Problem Statement

The task is to create a square matrix with dimensions n x n given a positive integer n. This matrix should be populated with the numbers from 1 to n^2. However, the unique requirement is that these numbers must be filled in a spiral order. Starting from the top-left corner, the numbers spiral inward towards the center in a clockwise fashion. This pattern presents an interesting challenge in matrix manipulation and iteration control as the matrix size grows with larger values of n.

Examples

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 and Intuition

Generating the Spiral Matrix:

1. Initial Setup:

   • Create an empty matrix of size n x n. This can be achieved using list comprehensions or nested loops. Each cell is initially marked with some placeholder or unassigned.

2. Navigation Setup:

   • Define movement directions for the spiral traversal. Typically, the cycle is right -> down -> left -> up repeated until the matrix is filled.

3. Boundary and State Control:

   • Keep track of the edges of the matrix (top, bottom, left, right). These boundaries will change whenever a row or a column is completely filled. For example, after moving right (filling top row), the top boundary shifts downward.
   • Control the traversal using a direction index, and change direction each time a boundary is reached or the next cell in the current direction is already filled.

4. Filling the Matrix:

   • Start at the top-left corner ([0][0]) and begin with moving right.
   • Place numbers continuously in the matrix from 1 to n^2, adjusting the position and direction based on the current state and boundaries.
   • Change the traversal direction and update boundaries as necessary until all positions in the matrix are filled.

5. Completion Check:

   • The loop can naturally end once the number to be placed exceeds n^2. At this point, each entry in the matrix from [0][0] to [n-1][n-1] will be filled as per the spiral rule.

Example Walk-through:

• For n = 3:

  • Start at [0][0], move right across the top row: Place 1, 2, 3.
  • Shift direction to down and move along the last column: Place 4, 5.
  • Continue spiraling to the left on the bottom row and then up to finish the middle of the matrix.
  • The resulting matrix: [[1, 2, 3], [8, 9, 4], [7, 6, 5]].

• For n = 1:

  • Only one element to place, resulting in: [[1]].

This approach ensures that we are constantly adjusting our boundaries and direction, effectively spiraling towards the center of the matrix. The constraints 1 <= n <= 20 are manageable with this method, ensuring all computations are contained within reasonable time and space complexity.

Solutions

class Solution {
public:
    vector<vector<int>> fillMatrix(int size) {
        vector<vector<int>> matrix(size, vector<int>(size));
        int number = 1;
        for (int level = 0; level < (size + 1) / 2; level++) {
            // fill rightwards
            for (int i = level; i < size - level; i++) {
                matrix[level][i] = number++;
            }
            // fill downwards
            for (int i = level + 1; i < size - level; i++) {
                matrix[i][size - level - 1] = number++;
            }
            // fill leftwards
            for (int i = size - level - 2; i >= level; i--) {
                matrix[size - level - 1][i] = number++;
            }
            // fill upwards
            for (int i = size - level - 2; i > level; i--) {
                matrix[i][level] = number++;
            }
        }
        return matrix;
    }
};