Leetcode 59: Spiral Matrix II
Solution to LeetCode 59: Spiral Matrix II Problem
Create an n x n matrix where numbers from 1 to n^2 are arranged in a spiral order starting from the top-left corner.
Problem
Approach
Steps
Complexity
Input: A single integer n representing the size of the square matrix.
Example: Input: n = 4
Constraints:
• 1 <= n <= 20
Output: An n x n matrix filled with numbers from 1 to n^2 in a spiral order.
Example: Output: [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]
Constraints:
• Output matrix should always have dimensions n x n.
Goal: Generate the matrix by placing numbers sequentially in a spiral pattern.
Steps:
• Initialize an n x n matrix with zeros.
• Set boundaries for rows and columns: top, bottom, left, and right.
• Iteratively fill the matrix: move right, down, left, and up while updating the boundaries.
• Stop when all numbers from 1 to n^2 have been placed.
Goal: The input size must be within the given range, and the matrix should conform to spiral order.
Steps:
• 1 <= n <= 20
Assumptions:
• The input is always a positive integer within the valid range.
• The matrix is square (n x n).
• Input: Input: n = 4
• Explanation: The numbers from 1 to 16 are filled in a 4x4 matrix in a clockwise spiral order.
• Input: Input: n = 2
• Explanation: A 2x2 matrix is filled with numbers from 1 to 4 in a spiral order.
• Input: Input: n = 1
• Explanation: A single number 1 fills the 1x1 matrix.
Approach: Use iterative boundary-based traversal to fill the matrix in a spiral order.
Observations:
• The spiral traversal involves updating the boundaries after each pass.
• The pattern follows clockwise movement: right, down, left, up.
• Boundaries shrink after each traversal, ensuring the spiral pattern.
Steps:
• Initialize a matrix with all zeros and boundary pointers for rows and columns.
• Iteratively move right, down, left, and up to fill numbers into the matrix.
• After each direction, update the respective boundary to ensure proper traversal.
• Stop when the number to be placed exceeds n^2.
Empty Inputs:
• Not applicable as input is guaranteed.
Large Inputs:
• Maximum n value, such as n = 20.
Special Values:
• Minimum n value, n = 1.
Constraints:
• Ensure the matrix dimensions are correct for edge cases.
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> matrix(n, vector<int>(n));
int num = 1, rowStart = 0, rowEnd = n - 1, colStart = 0, colEnd = n - 1;
while (rowStart <= rowEnd && colStart <= colEnd) {
// Top row
for (int col = colStart; col <= colEnd; col++) {
matrix[rowStart][col] = num++;
}
rowStart++;
// Right column
for (int row = rowStart; row <= rowEnd; row++) {
matrix[row][colEnd] = num++;
}
colEnd--;
// Bottom row
if (rowStart <= rowEnd) {
for (int col = colEnd; col >= colStart; col--) {
matrix[rowEnd][col] = num++;
}
rowEnd--;
}
// Left column
if (colStart <= colEnd) {
for (int row = rowEnd; row >= rowStart; row--) {
matrix[row][colStart] = num++;
}
colStart++;
}
}
return matrix;
}
1 : Function Declaration
vector<vector<int>> generateMatrix(int n) {
This line declares a function named `generateMatrix` that takes an integer `n` as input and returns a 2D vector representing the spiral matrix.
2 : Matrix Initialization
vector<vector<int>> matrix(n, vector<int>(n));
This line initializes a 2D vector `matrix` of size `n x n` with all elements set to 0.
3 : Variable Initialization
int num = 1, rowStart = 0, rowEnd = n - 1, colStart = 0, colEnd = n - 1;
This line initializes variables to keep track of the current number to be filled, the starting and ending row and column indices.
4 : Spiral Filling Loop
while (rowStart <= rowEnd && colStart <= colEnd) {
This loop continues as long as there are elements to be filled in the spiral pattern.
5 : Fill Top Row
for (int col = colStart; col <= colEnd; col++) {
matrix[rowStart][col] = num++;
}
This loop fills the top row of the current spiral layer, starting from the `colStart` column and moving to the `colEnd` column.
6 : Update Row Start
rowStart++;
The `rowStart` is incremented to move to the next row.
7 : Fill Right Column
for (int row = rowStart; row <= rowEnd; row++) {
matrix[row][colEnd] = num++;
}
This loop fills the right column of the current spiral layer, starting from the new `rowStart` and moving to the `rowEnd` row.
8 : Update Column End
colEnd--;
The `colEnd` is decremented to move to the previous column.
9 : Fill Bottom Row (Conditional)
if (rowStart <= rowEnd) {
This condition checks if there are still rows to be filled from the bottom.
10 : Fill Bottom Row
for (int col = colEnd; col >= colStart; col--) {
matrix[rowEnd][col] = num++;
}
This loop fills the bottom row of the current spiral layer, starting from the `colEnd` column and moving to the `colStart` column.
11 : Update Row End
rowEnd--;
The `rowEnd` is decremented to move to the previous row.
12 : Fill Left Column (Conditional)
if (colStart <= colEnd) {
This condition checks if there are still columns to be filled from the left.
13 : Fill Left Column
for (int row = rowEnd; row >= rowStart; row--) {
matrix[row][colStart] = num++;
}
This loop fills the left column of the current spiral layer, starting from the `rowEnd` row and moving to the `rowStart` row.
14 : Update Column Start
colStart++;
The `colStart` is incremented to move to the next column.
15 : Return the Matrix
return matrix;
The function returns the completed spiral matrix.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: Each number from 1 to n^2 is placed exactly once in the matrix.
Best Case: O(n^2)
Worst Case: O(n^2)
Description: The matrix itself requires O(n^2) space.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus