Spiral Matrix Iv - Leetcode Solution

Problem Statement:

Given an integer n, generate a square matrix filled with elements from 1 to n² in spiral order.

Example:

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

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

Approach:

In this problem, we need to generate a square matrix filled with numbers in spiral order. To solve this problem, we can use the following approach:

Step 1: Initialize an empty n*n matrix. Step 2: Initialize the four corners of the matrix (top, bottom, left, and right) to 0, n - 1, 0, and n - 1 respectively. Step 3: Set the counter to 1. Step 4: Loop until the counter is less than or equal to n * n. Step 5: Traverse the matrix elements in a spiral order and fill them with counter value. Step 6: Increment the counter value after adding it to the matrix element. Step 7: Adjust the top, bottom, left, and right corners accordingly. Step 8: Return the generated matrix.

Let's see the implementation of the above approach step by step.

Code:

class Solution: def generateMatrix(self, n): # Initialize an empty matrix of size n x n matrix = [[0] * n for _ in range(n)]

    # Initialize the four corners of the matrix
    top, bottom, left, right = 0, n - 1, 0, n - 1
    
    # Initialize the counter
    counter = 1
    
    # Traverse the matrix elements in a spiral order
    while counter <= n * n:
        for i in range(left, right + 1):
            matrix[top][i] = counter
            counter += 1
        top += 1
        
        for i in range(top, bottom + 1):
            matrix[i][right] = counter
            counter += 1
        right -= 1
        
        for i in range(right, left - 1, -1):
            matrix[bottom][i] = counter
            counter += 1
        bottom -= 1
        
        for i in range(bottom, top - 1, -1):
            matrix[i][left] = counter
            counter += 1
        left += 1
    
    # Return the generated matrix
    return matrix

In the above code, we have implemented the approach step by step. Let's see the explanation of each step.

Step 1: Initialize an empty n*n matrix.

We initialize an empty n*n matrix, where n is the input size.

matrix = [[0] * n for _ in range(n)]

Step 2: Initialize the four corners of the matrix (top, bottom, left, and right) to 0, n - 1, 0, and n - 1 respectively.

We initialize the four corners of the matrix (top, bottom, left, and right) to 0, n - 1, 0, and n - 1 respectively.

top, bottom, left, right = 0, n - 1, 0, n - 1

Step 3: Set the counter to 1.

We set the counter to 1.

counter = 1

Step 4: Loop until the counter is less than or equal to n * n.

We loop until the counter is less than or equal to n * n.

while counter <= n * n:

Step 5: Traverse the matrix elements in a spiral order and fill them with counter value.

We traverse the matrix elements in a spiral order and fill them with counter value.

for i in range(left, right + 1): matrix[top][i] = counter counter += 1 top += 1

    for i in range(top, bottom + 1):
        matrix[i][right] = counter
        counter += 1
    right -= 1
    
    for i in range(right, left - 1, -1):
        matrix[bottom][i] = counter
        counter += 1
    bottom -= 1
    
    for i in range(bottom, top - 1, -1):
        matrix[i][left] = counter
        counter += 1
    left += 1

Step 6: Increment the counter value after adding it to the matrix element.

We increment the counter value after adding it to the matrix element.

counter += 1

Step 7: Adjust the top, bottom, left, and right corners accordingly.

We adjust the top, bottom, left, and right corners accordingly.

top += 1 right -= 1 bottom -= 1 left += 1

Step 8: Return the generated matrix.

We return the generated matrix.

return matrix

Time Complexity:

The time complexity of this solution is O(n^2), where n is the input size. Since we are traversing all the n^2 elements of the matrix.

Space Complexity:

The space complexity of this solution is O(n^2), where n is the input size. Since we are creating a matrix of size n x n.

1