Spiral Matrix II

How it works

Instead of tracking four boundaries, we can use direction vectors to navigate the spiral. We start moving right and change direction (right -> down -> left -> up -> right...) whenever we hit a boundary or an already-filled cell. The direction change follows the pattern of rotating 90 degrees clockwise, which can be computed mathematically: if current direction is (dr, dc), the next direction is (dc, -dr).

Steps

1. Initialize an n x n matrix with zeros. Set starting position (r, c) = (0, 0) and direction (dr, dc) = (0, 1) (moving right).
2. For each value from 1 to n^2:
   • Place the value at position (r, c).
   • Check if the next position (with wraparound) is already filled.
   • If so, rotate direction by setting (dr, dc) = (dc, -dr).
   • Move to the next position: r += dr, c += dc.
3. Return the filled matrix.

Complexity

• Time complexity: O(n ^ 2)
• Space complexity: O(n ^ 2) for the output matrix.

Things to watch for

Incorrect Boundary Updates

Failing to update boundaries (top, bottom, left, right) after filling each edge leads to overwriting previously filled cells or skipping cells entirely. Each boundary must be adjusted immediately after its corresponding edge is filled.

Off-by-One in Range Calculations

When iterating along rows or columns, using inclusive vs exclusive bounds incorrectly causes cells to be missed or written twice. For example, after filling the top row from left to right, the next column fill should start from top + 1, not top.

Forgetting to Handle Odd-Sized Matrices

For odd values of n, the center cell requires special attention. If the loop condition or boundary updates are off, the center cell may be skipped or the loop may not terminate correctly. The direction-based approach handles this naturally, but boundary-based approaches need careful loop conditions.

from typing import List

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        mat = [[0] * n for _ in range(n)]
        r = c = 0
        dr, dc = 0, 1

        for val in range(n * n):
            mat[r][c] = val + 1
            if mat[(r + dr) % n][(c + dc) % n] != 0:
                dr, dc = dc, -dr
            r, c = r + dr, c + dc

        return mat

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> mat(n, vector<int>(n, 0));
        int r = 0, c = 0, dr = 0, dc = 1;

        for (int val = 0; val < n * n; val++) {
            mat[r][c] = val + 1;
            int nextR = (r + dr) % n, nextC = (c + dc) % n;
            if (nextR < 0) nextR += n;
            if (nextC < 0) nextC += n;
            if (mat[nextR][nextC] != 0) {
                int temp = dr;
                dr = dc;
                dc = -temp;
            }
            r += dr;
            c += dc;
        }

        return mat;
    }
};