Spiral Matrix Ii - Leetcode Solution

Problem Statement: Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

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

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

Approach: To solve this problem, we can generate a matrix of size nn and fill it with zeros. After this, we can traverse the matrix in a spiral order and fill it with integers from 1 to nn. We can achieve this by keeping track of the four edges of the matrix, i.e., top, bottom, left, and right. We start by filling the top row, then the right column, then the bottom row, and then the left column. We continue this process until all the elements of the matrix are filled.

Algorithm:

1. Create an empty n*n matrix filled with zeros
2. Initialize counter = 1
3. Initialize top, left, bottom, right pointers pointing to the first row, first column, last row, and last column of the matrix.
4. Traverse the matrix in a spiral order by filling each element with counter. Increment the counter after filling each element. a. Fill the top row from left to right (i.e., from left pointer to right pointer). b. Increment the top pointer. If top pointer > bottom pointer, break the traversal. c. Fill the right column from top to bottom (i.e., from top pointer to bottom pointer). d. Decrement the right pointer. If left pointer > right pointer, break the traversal. e. Fill the bottom row from right to left (i.e., from right pointer to left pointer). f. Decrement the bottom pointer. If top pointer > bottom pointer, break the traversal. g. Fill the left column from bottom to top (i.e., from bottom pointer to top pointer). h. Increment the left pointer. If left pointer > right pointer, break the traversal.
5. Return the matrix.

Code:

class Solution: def generateMatrix(self, n: int) -> List[List[int]]: # create an empty matrix filled with zeros matrix = [[0 for i in range(n)] for j in range(n)]

    counter = 1
    top, left, bottom, right = 0, 0, n-1, n-1
    
    while True:
        # fill the top row
        for i in range(left, right+1):
            matrix[top][i] = counter
            counter += 1
        top += 1
        if top > bottom:
            break
            
        # fill the right column
        for i in range(top, bottom+1):
            matrix[i][right] = counter
            counter += 1
        right -= 1
        if left > right:
            break
            
        # fill the bottom row
        for i in range(right, left-1, -1):
            matrix[bottom][i] = counter
            counter += 1
        bottom -= 1
        if top > bottom:
            break
            
        # fill the left column
        for i in range(bottom, top-1, -1):
            matrix[i][left] = counter
            counter += 1
        left += 1
        if left > right:
            break
            
    return matrix

Time Complexity: O(n^2) as we traverse all n^2 elements in the matrix.

Space Complexity: O(n^2) as we create a matrix of size n*n.

1