59. Spiral Matrix II

Problem Statement

link: https://leetcode.com/problems/spiral-matrix-ii/description/ https://leetcode.cn/problems/spiral-matrix-ii/description/

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

Example:

Input: n = 3 Output: [[1,2,3],[8,9,4],[7,6,5]]

Input: n = 1 Output: [[1]]

Solution Approach

The approach simulates the spiral movement by iteratively filling the matrix while changing direction when hitting boundaries or already-filled cells.

Algorithm

• Matrix Initialization: Create an n x n matrix initialized with zeroes and set up directions for right, down, left, and up movement.
• Spiral Filling: Starting from the top-left corner, follow the directions to fill the matrix in a spiral manner with numbers from 1 to (n^2).
• Direction Change: Whenever a boundary or an already-filled cell is encountered, change the direction clockwise and continue filling until the entire matrix is populated.

Implement

    class Solution:
      def generateMatrix(self, n: int) -> List[List[int]]:
          matrix = [[0] * n for _ in range(n)]
          directions = [(0,1),(1,0),(0,-1),(-1,0)]
          x, y, d = 0, 0, 0
          for i in range(1, n*n + 1):
              matrix[x][y] = i
              nx,ny = x + directions[d][0], y + directions[d][1]
              if nx < 0 or ny < 0 or nx >= n or ny >= n or matrix[nx][ny]:
                  d = (d + 1) % 4
              x += directions[d][0]
              y += directions[d][1]
          return matrix
         

    
    

Twitter  facebook  Email