Katkat
Back

Generate a Spiral Matrix

PinduoduoSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage matrix traversal coordinates and maintain state (direction and boundaries) while iteratively filling a grid.

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 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 1-9 fill the matrix starting at (0,0), moving right to (0,2), down to (2,2), left to (2,0), and finally up and right to the 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 correctly without overwriting values at the center of the matrix.

Hints

Hint 1

Define four boundaries for the current spiral layer: top, bottom, left, and right.

Hint 2

Use a loop to iterate through the matrix, updating the current boundary values after completing each side of the spiral.

Hint 3

Continue the process as long as the current number to be placed is less than or equal to n squared.

Follow-up questions

  • How would you modify this algorithm if you were asked to fill a rectangular matrix of size m x n instead of a square matrix?
  • What is the time and space complexity of your solution, and can it be optimized further?
  • If you were given a pre-filled matrix, how would you perform a 'spiral traversal' and return the elements in a single list?