Spiral Matrix in Python

Spiral Matrix Traversal

Have you ever wondered how to traverse a 2D array in a spiral order? This problem, commonly referred to as the Spiral Matrix in Python, is a popular coding interview question. The task involves traversing a matrix layer by layer, starting from the outermost elements and spiraling inward. Solving this challenge not only helps you understand 2D array traversal but also strengthens your skills in algorithm design. Curious to learn how to efficiently implement this in Python and master the concept of matrix traversal in Python? Let’s break it down into simple steps and solve it together!

Steps to Solve Spiral Matrix in Python

• Understand the Goal: Traverse the 2D array in a spiral order, starting from the top-left corner, moving right, down, left, and then upward in a circular pattern.
• Set Boundaries:
  • Define boundaries for the top, bottom, left, and right sides of the matrix.
  • Adjust these boundaries as you move through the matrix to avoid revisiting elements.
• Traverse the Matrix:
  • Move left to right along the top boundary.
  • Move top to bottom along the right boundary.
  • Move right to left along the bottom boundary (if still valid).
  • Move bottom to top along the left boundary (if still valid).
• Adjust the Boundaries: After completing each layer of traversal, shrink the boundaries inward to focus on the next layer.
• Store the Result: Append the visited elements to a result list in the order they are traversed.
• Handle Edge Cases: Account for edge cases like empty matrices or single-row/column matrices.
• Test the Solution: Use different matrix examples, such as:
  • Input: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
  • Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

Problem statement

Given a matrix of m x n elements, return all elements of the matrix in spiral order.

Example

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

Idea to solve

To solve the spiral matrix problem, you need to simulate the process of going around the matrix layer by layer. Start from the outermost layer and move inward, collecting elements in the required order.

Detailed explanation

• Initialize Boundaries: Set the initial boundaries for top, bottom, left, and right.
• Traverse the Matrix:
  • Move from left to right across the top row, then move the top boundary down.
  • Move from top to bottom along the right column, then move the right boundary left.
  • Move from right to left across the bottom row, then move the bottom boundary up.
  • Move from bottom to top along the left column, then move the left boundary right.
• Repeat until all elements are collected.

Full code in Python

Here's the complete Python code to solve the spiral matrix problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def spiralOrder(matrix):
    if not matrix:
        return []

    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while top <= bottom and left <= right:
        # Traverse from left to right
        for i in range(left, right + 1):
            result.append(matrix[top][i])
        top += 1

        # Traverse from top to bottom
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1

        if top <= bottom:
            # Traverse from right to left
            for i in range(right, left - 1, -1):
                result.append(matrix[bottom][i])
            bottom -= 1

        if left <= right:
            # Traverse from bottom to top
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1

    return result

# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print("Spiral order of the matrix:", spiralOrder(matrix))

Explanation of the code

• Initialize Boundaries: Set the initial boundaries for top, bottom, left, and right.
• Traverse the Matrix: Use a while loop to traverse the matrix in a spiral order by updating the boundaries and collecting elements in the result list.
• Return Result: After traversing the entire matrix, return the result list containing the elements in spiral order.

Conclusion

The Spiral Matrix in Python problem is a fascinating challenge that involves traversing a 2D array in a spiral order. This task strengthens your understanding of matrix traversal techniques while preparing you for common coding interview questions. Mastering this concept equips you with skills for solving real-world problems efficiently.