#54

Medium

LeetCode Problem Workspace

Spiral Matrix

Given an m x n matrix, return all elements in spiral order starting from the top-left corner.

Problem Statement

You are given an m x n matrix, where m is the number of rows and n is the number of columns. Your task is to return all elements of the matrix in spiral order, starting from the top-left corner and moving right, down, left, and up repeatedly.

For example, consider the matrix [[1,2,3],[4,5,6],[7,8,9]]. The elements should be returned in the order [1,2,3,6,9,8,7,4,5]. This problem is an array-plus-matrix simulation, where you simulate the process of visiting matrix elements while adjusting your traversal boundaries as you proceed.

Examples

Example 1

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Output: [1,2,3,6,9,8,7,4,5]

Example details omitted.

Example 2

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Example details omitted.

Constraints

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

Solution Approach

Simulate the Spiral Traversal

The approach is to simulate the traversal of the matrix while adjusting the boundaries. Start with top, bottom, left, and right pointers that define the boundaries of the matrix. Move through the matrix in the order: right, down, left, and up, adjusting the boundaries after each move. This ensures that all elements are visited in spiral order.

Adjust Boundaries Dynamically

Each time we finish traversing one side of the boundary (e.g., the top row), we adjust the respective boundary (move top pointer down after completing the top row). Similarly, adjust the bottom, left, and right pointers after completing the bottom row, left column, and right column respectively. This dynamic adjustment helps ensure that the traversal doesn't revisit already processed elements.

Handling Edge Cases

Edge cases include matrices that are only one row or column, or when the matrix dimensions are very small (1x1). These edge cases can be handled by ensuring the boundary conditions are checked during the traversal process. If boundaries overlap, the traversal should stop to avoid revisiting elements.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of elements in the matrix, which is O(m n). Space complexity is O(1) if the solution modifies the matrix in-place, but it could be O(m n) if a new array is created to store the result.

What Interviewers Usually Probe

Do you understand the process of adjusting boundaries dynamically in a spiral traversal?
Can you explain how the simulation approach helps to cover all matrix elements in spiral order?
Will you be able to handle edge cases such as 1x1 matrices or matrices with only one row or column?

Common Pitfalls or Variants

Common pitfalls

Not adjusting the boundaries after each pass (top, bottom, left, right) will cause revisiting the same elements.
Forgetting to handle matrices with only one row or column could result in out-of-bound errors or incorrect results.
Overcomplicating the solution by using unnecessary data structures instead of simulating the traversal directly.

Follow-up variants

Spiral matrix traversal with specific steps removed (e.g., no rightward movement allowed).
Spiral traversal of an n x n matrix where elements are updated instead of just being read.
Return the matrix elements in reverse spiral order.

FAQ

What is the primary strategy used to solve the Spiral Matrix problem?

The key strategy is simulating the traversal of the matrix by adjusting the boundaries dynamically after each row or column is processed.

How do you handle edge cases like 1x1 matrices?

Edge cases like 1x1 matrices are handled by ensuring the boundary conditions stop the traversal when there are no more elements to process.

What happens if we forget to adjust the boundaries during traversal?

If boundaries are not adjusted correctly, the algorithm will revisit already processed elements, leading to incorrect results.

Can we solve the Spiral Matrix problem without using extra space?

Yes, the problem can be solved with O(1) space complexity by modifying the boundaries in-place and not creating a new array for the output.

What is the time complexity of the Spiral Matrix problem?

The time complexity is O(m*n), where m is the number of rows and n is the number of columns, since each element is visited once.

terminal

Solution

Solution 1: Simulation

We can simulate the entire traversal process. We use $i$ and $j$ to represent the row and column of the current element being visited, and $k$ to represent the current direction. We use an array or hash table $\textit{vis}$ to record whether each element has been visited. Each time we visit an element, we mark it as visited, then move one step forward in the current direction. If moving forward results in an out-of-bounds condition or the element has already been visited, we change direction and continue moving forward until the entire matrix has been traversed.

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        dirs = (0, 1, 0, -1, 0)
        vis = [[False] * n for _ in range(m)]
        i = j = k = 0
        ans = []
        for _ in range(m * n):
            ans.append(matrix[i][j])
            vis[i][j] = True
            x, y = i + dirs[k], j + dirs[k + 1]
            if x < 0 or x >= m or y < 0 or y >= n or vis[x][y]:
                k = (k + 1) % 4
            i += dirs[k]
            j += dirs[k + 1]
        return ans

Solution 2: Simulation (Space Optimization)

Notice that the range of matrix element values is $[-100, 100]$. Therefore, we can add a large value, such as $300$, to the visited elements. This way, we only need to check if the visited element is greater than $100$, without needing extra space to record whether it has been visited. If we need to restore the original values of the visited elements, we can traverse the matrix again after the traversal is complete and subtract $300$ from all elements.

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        dirs = (0, 1, 0, -1, 0)
        vis = [[False] * n for _ in range(m)]
        i = j = k = 0
        ans = []
        for _ in range(m * n):
            ans.append(matrix[i][j])
            vis[i][j] = True
            x, y = i + dirs[k], j + dirs[k + 1]
            if x < 0 or x >= m or y < 0 or y >= n or vis[x][y]:
                k = (k + 1) % 4
            i += dirs[k]
            j += dirs[k + 1]
        return ans

Continue Practicing

#749 contain virus #832 flipping an image #63 unique paths ii