Solution For Spiral Matrix Ii
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:
- Create an empty n*n matrix filled with zeros
- Initialize counter = 1
- Initialize top, left, bottom, right pointers pointing to the first row, first column, last row, and last column of the matrix.
- 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. - 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.
Step by Step Implementation For Spiral Matrix Ii
public class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
if (n <= 0) return res;
int num = 1;
int rowStart = 0;
int rowEnd = n - 1;
int colStart = 0;
int colEnd = n - 1;
while (rowStart <= rowEnd && colStart <= colEnd) {
// go right
for (int i = colStart; i <= colEnd; i++) {
res[rowStart][i] = num++;
}
rowStart++;
// go down
for (int i = rowStart; i <= rowEnd; i++) {
res[i][colEnd] = num++;
}
colEnd--;
// go left
for (int i = colEnd; i >= colStart; i--) {
res[rowEnd][i] = num++;
}
rowEnd--;
// go up
for (int i = rowEnd; i >= rowStart; i--) {
res[i][colStart] = num++;
}
colStart++;
}
return res;
}
}def generateMatrix(n):
"""
:type n: int
:rtype: List[List[int]]
"""
# create an empty matrix
matrix = []
for i in range(n):
matrix.append([0] * n)
# define boundaries
top = 0
bottom = n - 1
left = 0
right = n - 1
num = 1
# fill in the matrix in a spiral pattern
while left <= right and top <= bottom:
for i in range(left, right + 1):
matrix[top][i] = num
num += 1
for i in range(top + 1, bottom):
matrix[i][right] = num
num += 1
for i in range(right, left - 1, -1):
matrix[bottom][i] = num
num += 1
for i in range(bottom - 1, top, -1):
matrix[i][left] = num
num += 1
left += 1
right -= 1
top += 1
bottom -= 1
return matrixvar generateMatrix = function(n) {
// create an empty n-by-n matrix
let matrix = [];
for (let i = 0; i < n; i++) {
matrix.push([]);
}
// define the four directions we can move in
let directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
// starting position and direction
let position = [0, 0];
let direction = 0;
// fill in the matrix in a spiral pattern
for (let i = 1; i <= n * n; i++) {
matrix[position[0]][position[1]] = i;
// figure out next position
let nextPosition = [position[0] + directions[direction][0], position[1] + directions[direction][1]];
// if the next position is out of bounds or already filled, change direction
if (nextPosition[0] < 0 || nextPosition[0] >= n || nextPosition[1] < 0 || nextPosition[1] >= n || matrix[nextPosition[0]][nextPosition[1]] !== 0) {
direction = (direction + 1) % 4;
nextPosition = [position[0] + directions[direction][0], position[1] + directions[direction][1]];
}
position = nextPosition;
}
return matrix;
};class Solution {
public:
vector> generateMatrix(int n) {
// Create an n x n matrix
vector> matrix(n, vector(n));
// Initialize start row, start column, end row, end column
int r1 = 0, c1 = 0, r2 = n - 1, c2 = n - 1;
// Initialize counter
int num = 1;
// Loop while start row is less than or equal to end row and start column is less than or equal to end column
while (r1 <= r2 && c1 <= c2) {
// Loop from start column to end column
for (int c = c1; c <= c2; c++) {
// Set current element to counter
matrix[r1][c] = num;
// Increment counter
num++;
}
// Increment start row
r1++;
// Loop from start row to end row
for (int r = r1; r <= r2; r++) {
// Set current element to counter
matrix[r][c2] = num;
// Increment counter
num++;
}
// Decrement end column
c2--;
// Loop from end column to start column
for (int c = c2; c >= c1; c--) {
// Set current element to counter
matrix[r2][c] = num;
// Increment counter
num++;
}
// Decrement end row
r2--;
// Loop from end row to start row
for (int r = r2; r >= r1; r--) {
// Set current element to counter
matrix[r][c1] = num;
// Increment counter
num++;
}
// Increment start column
c1++;
}
// Return matrix
return matrix;
}
}; public class Solution {
public int[][] GenerateMatrix(int n) {
// Create an empty spiral matrix
int[][] spiral = new int[n][n];
// Initialize value to 1
int value = 1;
// Find the starting row and column for the first element
int sr = 0, sc = 0;
// Loop through the matrix until all elements are filled
while (sr < n && sc < n) {
// Loop through the current row from left to right
for (int i = sc; i < n; i++) {
// Insert the value into the current cell
spiral[sr][i] = value;
// Increment value by 1
value++;
}
// Move to the next row down
sr++;
// Loop through the current column from top to bottom
for (int i = sr; i < n; i++) {
// Insert the value into the current cell
spiral[i][n-1] = value;
// Increment value by 1
value++;
}
// Move to the next column to the left
n--;
// Loop through the current row from right to left
if (sr < n) {
for (int i = n-1; i >= sc; i--) {
// Insert the value into the current cell
spiral[n-1][i] = value;
// Increment value by 1
value++;
}
// Move to the next row up
n--;
}
// Loop through the current column from bottom to top
if (sc < n) {
for (int i = n-1; i >= sr; i--) {
// Insert the value into the current cell
spiral[i][sc] = value;
// Increment value by 1
value++;
}
// Move to the next column to the right
sc++;
}
}
// Return the completed spiral matrix
return spiral;
}
}