Generate a Spiral Matrix

Question

The question asks the candidate to generate a spiral matrix given a specific number of rows and columns.

Codemia · Accepted Answer

To generate a spiral matrix, we can visualize the traversal of the matrix in a clockwise direction. We will maintain boundaries for the top, bottom, left, and right edges of the matrix and fill in values while adjusting these boundaries as we complete each layer of the spiral.

1. Initialize an empty matrix of size `rows x cols`.
2. Set boundaries: `top`, `bottom`, `left`, and `right`.
3. Use a loop to fill numbers from 1 to `rows * cols`:
   - Traverse from left to right along the `top` boundary, then increment `top`.
   - Traverse from top to bottom along the `right` boundary, then decrement `right`.
   - If there are remaining rows, traverse from right to left along the `bottom` boundary, then decrement `bottom`.
   - If there are remaining columns, traverse from bottom to top along the `left` boundary, then increment `left`.
4. Repeat until all elements are filled.

The time complexity of this algorithm is O(n), where n is the total number of elements in the matrix (i.e., `rows * cols`). The space complexity is O(1) if we consider the output matrix as the only additional space used.

```python
def generate_spiral_matrix(rows, cols):
    if rows == 0 or cols == 0:
        return []
    matrix = [[0] * cols for _ in range(rows)]
    top, bottom, left, right = 0, rows - 1, 0, cols - 1
    num = 1

while top <= bottom and left <= right:
        for i in range(left, right + 1):
            matrix[top][i] = num
            num += 1
        top += 1

for i in range(top, bottom + 1):
            matrix[i][right] = num
            num += 1
        right -= 1

if top <= bottom:
            for i in range(right, left - 1, -1):
                matrix[bottom][i] = num
                num += 1
            bottom -= 1

if left <= right:
            for i in range(bottom, top - 1, -1):
                matrix[i][left] = num
                num += 1
            left += 1

return matrix
```

Consider edge cases such as when either `rows` or `cols` is zero. In such cases, the function should return an empty list. Additionally, for a single row or single column, the function should still correctly output the spiral arrangement.

Generate a Spiral Matrix

Pinduoduo

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Pinduoduo Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string