HomeLeetcode59. Spiral Matrix II - Leetcode Solutions

59. Spiral Matrix II – Leetcode Solutions

Description:

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

Examples:

Example 1:

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

Example 2:

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

Solution in Python:

Python
from typing import List

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # Initialize the n x n matrix with zeros
        matrix = [[0] * n for _ in range(n)]
        
        # Define the boundaries of the spiral traversal
        left, right = 0, n - 1
        top, bottom = 0, n - 1
        
        # Start the number to fill the matrix with
        num = 1
        
        while left <= right and top <= bottom:
            # Traverse from left to right on the topmost 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 on the rightmost 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 on the bottommost row
            if top <= bottom:  # Check if there is still a row to traverse
                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 on the leftmost column
            if left <= right:  # Check if there is still a column to traverse
                for i in range(bottom, top - 1, -1):
                    matrix[i][left] = num
                    num += 1
                left += 1  # Move the left boundary right
        
        return matrix

Explanation of the Code:

  1. Matrix Initialization:
    • We start by initializing an n x n matrix filled with zeros using a list comprehension: matrix = [[0] * n for _ in range(n)].
  2. Boundary Definitions:
    • We define four boundaries for the traversal:
      • left (initially 0): the leftmost column to be filled.
      • right (initially n - 1): the rightmost column to be filled.
      • top (initially 0): the topmost row to be filled.
      • bottom (initially n - 1): the bottommost row to be filled.
  3. Number Initialization:
    • We initialize num to 1, which is the first number to be filled in the matrix.
  4. Spiral Traversal:
    • We use a while loop to continue the traversal until all boundaries collapse (left <= right and top <= bottom).
    • Left to Right (Top Row):
      • Traverse from left to right along the top row and fill the numbers.
      • Increment the top boundary by 1 to move to the next row.
    • Top to Bottom (Right Column):
      • Traverse from top to bottom along the right column and fill the numbers.
      • Decrement the right boundary by 1 to move to the next column.
    • Right to Left (Bottom Row):
      • If there are remaining rows (top <= bottom), traverse from right to left along the bottom row and fill the numbers.
      • Decrement the bottom boundary by 1 to move to the previous row.
    • Bottom to Top (Left Column):
      • If there are remaining columns (left <= right), traverse from bottom to top along the left column and fill the numbers.
      • Increment the left boundary by 1 to move to the next column.
  5. Returning the Matrix:
    • Finally, the filled matrix is returned as the result.

This approach ensures that the matrix is filled in a spiral order efficiently.

Solution in Javascript:

JavaScript
/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    // Initialize the n x n matrix with zeros
    const matrix = Array.from({ length: n }, () => Array(n).fill(0));

    // Define the boundaries of the spiral traversal
    let left = 0, right = n - 1;
    let top = 0, bottom = n - 1;

    // Start the number to fill the matrix with
    let num = 1;

    while (left <= right && top <= bottom) {
        // Traverse from left to right on the topmost row
        for (let j = left; j <= right; j++) {
            matrix[top][j] = num++;
        }
        top++;  // Move the top boundary down

        // Traverse from top to bottom on the rightmost column
        for (let i = top; i <= bottom; i++) {
            matrix[i][right] = num++;
        }
        right--;  // Move the right boundary left

        // Traverse from right to left on the bottommost row
        if (top <= bottom) {  // Check if there is still a row to traverse
            for (let j = right; j >= left; j--) {
                matrix[bottom][j] = num++;
            }
            bottom--;  // Move the bottom boundary up
        }

        // Traverse from bottom to top on the leftmost column
        if (left <= right) {  // Check if there is still a column to traverse
            for (let i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++;  // Move the left boundary right
        }
    }

    return matrix;
};

Solution in Java:

Java
class Solution {
    public int[][] generateMatrix(int n) {
        // Initialize the n x n matrix with zeros
        int[][] matrix = new int[n][n];

        // Define the boundaries of the spiral traversal
        int left = 0, right = n - 1;
        int top = 0, bottom = n - 1;

        // Start the number to fill the matrix with
        int num = 1;

        while (left <= right && top <= bottom) {
            // Traverse from left to right on the topmost row
            for (int j = left; j <= right; j++) {
                matrix[top][j] = num++;
            }
            top++;  // Move the top boundary down

            // Traverse from top to bottom on the rightmost column
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;  // Move the right boundary left

            // Traverse from right to left on the bottommost row
            if (top <= bottom) {  // Check if there is still a row to traverse
                for (int j = right; j >= left; j--) {
                    matrix[bottom][j] = num++;
                }
                bottom--;  // Move the bottom boundary up
            }

            // Traverse from bottom to top on the leftmost column
            if (left <= right) {  // Check if there is still a column to traverse
                for (int i = bottom; i >= top; i--) {
                    matrix[i][left] = num++;
                }
                left++;  // Move the left boundary right
            }
        }

        return matrix;
    }
}

Solution in C#:

C#
public class Solution {
    public int[][] GenerateMatrix(int n) {
        // Initialize the n x n matrix with zeros
        int[][] matrix = new int[n][];
        for (int i = 0; i < n; i++) {
            matrix[i] = new int[n];
        }

        // Define the boundaries of the spiral traversal
        int left = 0, right = n - 1;
        int top = 0, bottom = n - 1;

        // Start the number to fill the matrix with
        int num = 1;

        while (left <= right && top <= bottom) {
            // Traverse from left to right on the topmost row
            for (int j = left; j <= right; j++) {
                matrix[top][j] = num++;
            }
            top++;  // Move the top boundary down

            // Traverse from top to bottom on the rightmost column
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;  // Move the right boundary left

            // Traverse from right to left on the bottommost row
            if (top <= bottom) {  // Check if there is still a row to traverse
                for (int j = right; j >= left; j--) {
                    matrix[bottom][j] = num++;
                }
                bottom--;  // Move the bottom boundary up
            }

            // Traverse from bottom to top on the leftmost column
            if (left <= right) {  // Check if there is still a column to traverse
                for (int i = bottom; i >= top; i--) {
                    matrix[i][left] = num++;
                }
                left++;  // Move the left boundary right
            }
        }

        return matrix;
    }
}

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular