59.Spiral_Matrix_II(Medium).md

59. Spiral Matrix II (Medium)

Date and Time: Apr 3, 2025

Link: https://leetcode.com/problems/spiral-matrix-ii

Walk-through:

This question can be solved in similar method in 54. Spiral Matrix, we use four variables l, r, t, b to fill in by l->r, t->b, r->l, b->t directions.

Again, we are checking if t <= b and if l <= r before process r->l and b->t, because after the first two directions, we update t, r accordingly, if t > b or l > r means that direction is not valid anymore (out of bound).

Python Solution:

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # Keep track of l, r, t, b
        # Follow the l->r, t->b, r->l, b->t order to fill elements
        # TC: O(n^2), SC: O(1)
        area = [[1] * n for _ in range(n)]
        l, r, t, b = 0, n-1, 0, n-1
        curr = 1
        while l <= r and t <= b:
            # l->r, update t
            for i in range(l, r+1):
                area[t][i] = curr
                curr += 1
            t += 1
            # t->b, update r
            for i in range(t, b+1):
                area[i][r] = curr
                curr += 1
            r -= 1
            # r->l
            if t <= b:
                for i in range(r, l-1, -1):
                    area[b][i] = curr
                    curr += 1
                b -= 1
            # b->t
            if l <= r:
                for i in range(b, t-1, -1):
                    area[i][l] = curr
                    curr += 1
                l += 1
        return area

Time Complexity: $O(n^2)$
Space Complexity: $O(1)$