LeetCode Solutions Blog

Spiral Matrix II

Number: 59

Difficulty: Medium

Paid? No

Problem Description

Given a positive integer n, create an n x n matrix filled with elements from 1 to n² arranged in spiral order.

Key Insights

Use four pointers (top, bottom, left, right) to keep track of the matrix boundaries.
Traverse the matrix in a spiral: move right along the top row, then down the right column, left along the bottom row, and finally up the left column.
Update the boundary pointers after each complete traversal of one side.
Continue until all numbers from 1 to n² are filled into the matrix.

Space and Time Complexity

Time Complexity: O(n²)
Space Complexity: O(n²) (required for the output matrix)

Solution

We simulate the spiral movement by initializing four pointers: top, bottom, left, and right, which denote the current boundaries of the matrix that have not yet been filled. For each iteration, we:

Traverse from left to right along the top boundary, then increment the top pointer.
Traverse from top to bottom along the right boundary, then decrement the right pointer.
If there are rows remaining, traverse from right to left along the bottom boundary, then decrement the bottom pointer.
If there are columns remaining, traverse from bottom to top along the left boundary, then increment the left pointer. This algorithm ensures that the matrix is filled in a spiral order until all numbers are placed.

Code Solutions

# Function to generate spiral matrix of size n x n
def generateMatrix(n):
    # Initialize an n x n matrix with zeros
    matrix = [[0] * n for _ in range(n)]
    # Initialize the starting number to fill
    num = 1
    # Set the initial boundaries for rows and columns
    top, bottom = 0, n - 1
    left, right = 0, n - 1
    
    # Continue the loop until the boundaries are valid
    while top <= bottom and left <= right:
        # Traverse from left to right along the top row
        for j in range(left, right + 1):
            matrix[top][j] = num
            num += 1
        top += 1  # Move the top boundary down
        
        # Traverse from top to bottom along the right column
        for i in range(top, bottom + 1):
            matrix[i][right] = num
            num += 1
        right -= 1  # Move the right boundary left
        
        # Traverse from right to left along the bottom row if still in valid bounds
        if top <= bottom:
            for j in range(right, left - 1, -1):
                matrix[bottom][j] = num
                num += 1
            bottom -= 1  # Move the bottom boundary up
        
        # Traverse from bottom to top along the left column if still in valid bounds
        if left <= right:
            for i in range(bottom, top - 1, -1):
                matrix[i][left] = num
                num += 1
            left += 1  # Move the left boundary right

    return matrix

# Example usage:
print(generateMatrix(3))