Katkat
Back

Generate a Matrix in Spiral Order

PinduoduoSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to simulate a specific traversal pattern in a 2D grid and maintain precise boundary pointers to fill the matrix correctly.

Problem Statement

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order, starting from the top-left corner and moving clockwise.

Function Signature

def generate_spiral_matrix(n: int) -> list[list[int]]:

Constraints

  • 1 <= n <= 20

Examples

Example 1:

  • Input: n = 3
  • Output: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
  • Explanation: The numbers fill the matrix clockwise: 1, 2, 3 (top row), 4, 5 (right column), 6, 7 (bottom row), 8 (left column), 9 (center).

Example 2:

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

Edge Cases

  • n = 1: The matrix should contain only the value 1.
  • Even vs. Odd n: Ensure the spiral completes in the center for odd n and fills the inner-most square for even n.

Hints

Hint 1

Use four variables to track the current boundaries: top, bottom, left, and right.

Hint 2

After filling a row or column, adjust the corresponding boundary inward to signify that the row or column has been processed.

Hint 3

Run a loop until the counter variable exceeds n squared, updating the direction after each boundary is exhausted.

Follow-up questions

  • How would you modify this algorithm to generate a spiral matrix of size `m x n` instead of `n x n`?
  • What is the time and space complexity of your solution, and can you optimize the space if the matrix is very large?
  • If the input `n` were significantly larger (e.g., 10^5), how would you determine the value at a specific coordinate `(r, c)` without generating the entire matrix?