59. Spiral Matrix II - Explanation

Description

You are 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 = 2

Output: [[1,2],[4,3]]

Example 3:

Input: n = 1

Output: [[1]]

Constraints:

1 <= n <= 20

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Iteration

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        mat = [[0] * n for _ in range(n)]
        left, right = 0, n - 1
        top, bottom = 0, n - 1
        val = 1

        while left <= right:
            # Fill every val in top row
            for c in range(left, right + 1):
                mat[top][c] = val
                val += 1
            top += 1

            # Fill every val in right col
            for r in range(top, bottom + 1):
                mat[r][right] = val
                val += 1
            right -= 1

            # Fill every val in bottom row (reverse order)
            for c in range(right, left - 1, -1):
                mat[bottom][c] = val
                val += 1
            bottom -= 1

            # Fill every val in the left col (reverse order)
            for r in range(bottom, top - 1, -1):
                mat[r][left] = val
                val += 1
            left += 1

        return mat

Time & Space Complexity

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

2. Recursion

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

        def fill(left, right, top, bottom, val):
            if left > right or top > bottom:
                return

            # Fill every val in top row
            for c in range(left, right + 1):
                mat[top][c] = val
                val += 1
            top += 1

            # Fill every val in right col
            for r in range(top, bottom + 1):
                mat[r][right] = val
                val += 1
            right -= 1

            # Fill every val in bottom row (reverse order)
            for c in range(right, left - 1, -1):
                mat[bottom][c] = val
                val += 1
            bottom -= 1

            # Fill every val in the left col (reverse order)
            for r in range(bottom, top - 1, -1):
                mat[r][left] = val
                val += 1
            left += 1

            # Recur for the inner layer
            fill(left, right, top, bottom, val)

        fill(0, n - 1, 0, n - 1, 1)
        return mat

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity:
- $O(n)$ space for recursion stack.
- $O(n ^ 2)$ space for the output matrix.

3. Iteration (Optimal)

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

Time & Space Complexity

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