We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Spiral Matrix II

Difficulty: Medium

Problem Description

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

Key Insights

  • The matrix is filled in a spiral pattern starting from the top-left corner.
  • The filling direction changes between right, down, left, and up as the boundaries of the matrix are reached.
  • Maintaining boundaries (top, bottom, left, right) helps to control the filling of the matrix.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1) (excluding the output matrix)

Solution

To solve the problem, we can use a 2D array (matrix) to store the values. We define boundaries for our spiral traversal: top, bottom, left, and right. We will fill the matrix by iterating through these boundaries in a specific order:

  1. Start at the top row, moving from the left boundary to the right boundary.
  2. Move down the right column.
  3. If there are remaining rows, fill the bottom row from right to left.
  4. Move up the left column if there are remaining columns.
  5. Adjust the boundaries after each pass and repeat until the entire matrix is filled.

Code Solutions

def generateMatrix(n):
    # Initialize an n x n matrix with zeros
    matrix = [[0] * n for _ in range(n)]
    left, right, top, bottom = 0, n - 1, 0, n - 1
    num = 1

    while left <= right and top <= bottom:
        # Fill top row
        for i in range(left, right + 1):
            matrix[top][i] = num
            num += 1
        top += 1

        # Fill right column
        for i in range(top, bottom + 1):
            matrix[i][right] = num
            num += 1
        right -= 1

        if top <= bottom:
            # Fill bottom row
            for i in range(right, left - 1, -1):
                matrix[bottom][i] = num
                num += 1
            bottom -= 1

        if left <= right:
            # Fill left column
            for i in range(bottom, top - 1, -1):
                matrix[i][left] = num
                num += 1
            left += 1

    return matrix
← Back to All Questions