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 matrix
var 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; } }