Spiral Matrix II
#880 Most AskedMedium
Spiral Matrix II #880 Most Asked
Medium
1 view
Topics:
Arrays
Given a positive integer n, generate an n x n 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]]
Constraints:
1 <= n <= 20
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the expected data type of 'n'? Can I assume it's always a positive integer?
- For small values of 'n' such as 0 or 1, what should the function return?
- Could 'n' be very large, and should I be concerned about integer overflow when calculating the values to fill into the matrix?
- What is the expected format for the output matrix? Should it be a list of lists or another data structure?
- Is the spiral path always clockwise and starting from the top-left corner?
Brute Force Solution
Approach
Imagine walking around the outside of a square and filling in numbers one by one, then spiraling inwards. The brute force approach simulates this filling process directly, step by step, by manually keeping track of where you are and where you're allowed to go next.
Here's how the algorithm would work step-by-step:
- Start at the top-left corner of the square.
- Place the number 1 in that spot.
- Move to the right and place the number 2.
- Continue moving to the right, placing increasing numbers, until you hit the edge of the square or run into a spot that's already filled.
- When you can't move right anymore, try moving down. If you can, place the next number there and continue moving down.
- If you can't move down, try moving left. If you can, place the next number there and continue moving left.
- If you can't move left, try moving up. If you can, place the next number there and continue moving up.
- Keep repeating the right, down, left, up pattern, placing numbers as you go, until you've placed all the numbers from 1 up to the square's size times itself.
Code Implementation
def spiral_matrix_ii(matrix_size):
matrix = [[0] * matrix_size for _ in range(matrix_size)]
current_number = 1
row = 0
column = 0
row_direction = 0
column_direction = 1
for _ in range(matrix_size * matrix_size):
matrix[row][column] = current_number
current_number += 1
next_row = row + row_direction
next_column = column + column_direction
# Check to see if next move is out of bounds or spot is filled
if (next_row < 0 or next_row >= matrix_size or
next_column < 0 or next_column >= matrix_size or
matrix[next_row][next_column] != 0):
# Change direction when encountering a filled cell
if column_direction == 1:
row_direction = 1
column_direction = 0
elif row_direction == 1:
row_direction = 0
column_direction = -1
elif column_direction == -1:
row_direction = -1
column_direction = 0
else:
row_direction = 0
column_direction = 1
next_row = row + row_direction
next_column = column + column_direction
row = next_row
column = next_column
return matrixBig(O) Analysis
Time Complexity
O(n²) – The algorithm iterates through each cell of the n x n matrix exactly once, assigning a value to it. The number of cells in the matrix is n², where n is the input representing the dimension of the square matrix. The algorithm essentially fills each cell in a spiral order. Therefore, the time complexity is directly proportional to the number of cells it visits, resulting in O(n²). There are no nested loops that would increase the time complexity beyond quadratic time.
Space Complexity
O(N^2) – The algorithm creates an N x N matrix to store the spiral numbers. This matrix represents the primary auxiliary space used because it's separate from the input, which is just the integer N representing the dimensions. Therefore, the space required grows proportionally to the square of the input size N. The space complexity is then O(N^2).
Optimal Solution
Approach
The optimal approach involves filling the matrix layer by layer, moving in a spiral pattern. We simulate the movement in a clockwise direction, filling the top row, then the right column, then the bottom row, and finally the left column, and then repeating this process inwards until the center is reached.
Here's how the algorithm would work step-by-step:
- Imagine the matrix as a series of square layers nested inside each other.
- Start filling the outermost layer moving from left to right along the top.
- Continue filling down the right side.
- Then, fill the bottom from right to left.
- Next, fill the left side moving up.
- Move inward to the next layer and repeat the process of filling the top, right, bottom, and left until you reach the center of the matrix.
- Keep track of the current number to be filled in, incrementing it at each position.
Code Implementation
def generate_spiral_matrix(matrix_size):
spiral_matrix = [[0] * matrix_size for _ in range(matrix_size)]
current_number = 1
start_row, end_row = 0, matrix_size - 1
start_col, end_col = 0, matrix_size - 1
while start_row <= end_row and start_col <= end_col:
# Traverse top row
for column in range(start_col, end_col + 1):
spiral_matrix[start_row][column] = current_number
current_number += 1
start_row += 1
# Traverse right column
for row in range(start_row, end_row + 1):
spiral_matrix[row][end_col] = current_number
current_number += 1
end_col -= 1
# This condition checks if inner layer exists
if start_row <= end_row and start_col <= end_col:
# Traverse bottom row
for column in range(end_col, start_col - 1, -1):
spiral_matrix[end_row][column] = current_number
current_number += 1
end_row -= 1
# Traverse left column
for row in range(end_row, start_row - 1, -1):
spiral_matrix[row][start_col] = current_number
current_number += 1
start_col += 1
return spiral_matrixBig(O) Analysis
Time Complexity
O(n²) – The algorithm fills an n x n matrix layer by layer in a spiral pattern. Each cell in the matrix is visited and assigned a value exactly once. The number of cells in an n x n matrix is n². Therefore, the algorithm performs a constant amount of work for each of the n² cells. Consequently, the time complexity is directly proportional to the number of elements in the matrix, which is n², resulting in a time complexity of O(n²).
Space Complexity
O(1) – The algorithm constructs the spiral matrix in-place. It only uses a few integer variables to keep track of the current number being filled, row indices, and column indices during the traversal of the matrix. These variables consume a constant amount of extra space, irrespective of the input size N (where N is the dimension of the n x n matrix). Therefore, the auxiliary space complexity is O(1).
Edge Cases
| Case | How to Handle |
|---|---|
| n is zero or negative | Return an empty matrix immediately as a spiral matrix of size n <= 0 is not defined. |
| n is one | Return a 1x1 matrix with the single element 1. |
| n is a large number (integer overflow potential for calculating total elements) | While unlikely with typical constraints, use long integers if language constraints require it to prevent possible overflow during element assignment in extremely large n. |
| Integer overflow when incrementing the counter | The counter increment is checked only to n*n so integer limit checks aren't needed unless n*n is extremely large, if so, proper overflow checks should be implemented. |
| Incorrect loop termination leading to out-of-bounds access | The carefully managed boundaries (top, bottom, left, right) ensure the algorithm only iterates through valid matrix cells. |
| Confusing the order of traversal (right, down, left, up) | Maintain a consistent traversal order and update boundary variables after each layer is completed to prevent incorrect spiral formation. |
| Incorrect boundary updates leading to double processing of elements | Update boundaries (top, bottom, left, right) only after a full side is traversed to ensure correct spiral construction without redundant entries. |
| Memory allocation issues for very large n | Pre-allocate the matrix and ensure sufficient memory to avoid runtime errors, and consider using generators if possible to create the matrix in smaller chunks. |
n is zero or negative
How to Handle:
Return an empty matrix immediately as a spiral matrix of size n <= 0 is not defined.
n is one
How to Handle:
Return a 1x1 matrix with the single element 1.
n is a large number (integer overflow potential for calculating total elements)
How to Handle:
While unlikely with typical constraints, use long integers if language constraints require it to prevent possible overflow during element assignment in extremely large n.
Integer overflow when incrementing the counter
How to Handle:
The counter increment is checked only to n*n so integer limit checks aren't needed unless n*n is extremely large, if so, proper overflow checks should be implemented.
Incorrect loop termination leading to out-of-bounds access
How to Handle:
The carefully managed boundaries (top, bottom, left, right) ensure the algorithm only iterates through valid matrix cells.
Confusing the order of traversal (right, down, left, up)
How to Handle:
Maintain a consistent traversal order and update boundary variables after each layer is completed to prevent incorrect spiral formation.
Incorrect boundary updates leading to double processing of elements
How to Handle:
Update boundaries (top, bottom, left, right) only after a full side is traversed to ensure correct spiral construction without redundant entries.
Memory allocation issues for very large n
How to Handle:
Pre-allocate the matrix and ensure sufficient memory to avoid runtime errors, and consider using generators if possible to create the matrix in smaller chunks.
0/1037 Bloomberg LP questions completed
0/1037 completed
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
