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 matrixExplanation of the Code:
- Matrix Initialization:
- We start by initializing an
n x nmatrix filled with zeros using a list comprehension:matrix = [[0] * n for _ in range(n)].
- We start by initializing an
- Boundary Definitions:
- We define four boundaries for the traversal:
left(initially 0): the leftmost column to be filled.right(initiallyn - 1): the rightmost column to be filled.top(initially 0): the topmost row to be filled.bottom(initiallyn - 1): the bottommost row to be filled.
- We define four boundaries for the traversal:
- Number Initialization:
- We initialize
numto 1, which is the first number to be filled in the matrix.
- We initialize
- Spiral Traversal:
- We use a
whileloop to continue the traversal until all boundaries collapse (left <= rightandtop <= bottom). - Left to Right (Top Row):
- Traverse from
lefttorightalong thetoprow and fill the numbers. - Increment the
topboundary by 1 to move to the next row.
- Traverse from
- Top to Bottom (Right Column):
- Traverse from
toptobottomalong therightcolumn and fill the numbers. - Decrement the
rightboundary by 1 to move to the next column.
- Traverse from
- Right to Left (Bottom Row):
- If there are remaining rows (
top <= bottom), traverse fromrighttoleftalong thebottomrow and fill the numbers. - Decrement the
bottomboundary by 1 to move to the previous row.
- If there are remaining rows (
- Bottom to Top (Left Column):
- If there are remaining columns (
left <= right), traverse frombottomtotopalong theleftcolumn and fill the numbers. - Increment the
leftboundary by 1 to move to the next column.
- If there are remaining columns (
- We use a
- 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;
}
}