Printing a 2D matrix in spiral form is a popular interview problem that involves traversing the elements in a specific order. This article explains the problem, its solution, and a Python implementation. We’ll also provide test cases, algorithm breakdowns, and tips to understand and visualize this problem better.
Problem Statement
Given a matrix of size M×NM \times NM×N, print its elements in spiral order. The traversal begins from the top-left corner and moves as follows:
Initialize Boundaries: Define the boundaries of the matrix: top, bottom, left, and right.
Traverse Layers:
Traverse from left to right across the top boundary.
Traverse from top to bottom along the right boundary.
Traverse from right to left across the bottom boundary.
Traverse from bottom to top along the left boundary.
Update Boundaries: After each traversal, adjust the boundaries to exclude the traversed layer.
Stop Condition: Repeat the steps until all elements are traversed.
Python Implementation
python
defspiral_order(matrix):
"""
Print the elements of a 2D array in spiral order.
Args:
matrix (list of list of int): Input 2D matrix.
Returns:
list: List of elements in spiral order.
"""ifnot matrix ornot matrix[0]:
return []top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
result = []while top <= bottom and left <= right:
# Traverse from left to right across the top rowfor i inrange(left, right + 1):
result.append(matrix[top][i])
top += 1# Traverse from top to bottom along the right columnfor i inrange(top, bottom + 1):
result.append(matrix[i][right])
right -= 1# Traverse from right to left across the bottom rowif top <= bottom:
for i inrange(right, left - 1, -1):
result.append(matrix[bottom][i])
bottom -= 1# Traverse from bottom to top along the left columnif left <= right:
for i inrange(bottom, top - 1, -1):
result.append(matrix[i][left])
left += 1return result# Example Test Cases
matrix = [
[1, 2, 3, 4, 5, 6],
[7, 8, 9, 10, 11, 12],
[13, 14, 15, 16, 17, 18]
]
print(spiral_order(matrix)) # Output: [1, 2, 3, 4, 5, 6, 12, 18, 17, 16, 15, 14, 13, 7, 8, 9, 10, 11]
Time Complexity
O(M * N): Each element is visited exactly once.
Visual Explanation
Diagram of Spiral Traversal
Visualize the traversal layer by layer:
Highlight the top row.
Highlight the rightmost column.
Highlight the bottom row.
Highlight the leftmost column.
SEO-Optimized Subheadings
What Is Spiral Order Matrix Printing?
Step-by-Step Explanation of Spiral Matrix Algorithm
Python Code for Spiral Matrix Traversal
Time and Space Complexity of Spiral Order Printing
Applications of Spiral Order Traversal in Real-Life Scenarios
Suggested Visuals
Input Matrix Diagram: Annotated matrix showing each traversal step.
Output Spiral Path: Graphically represent the spiral order with arrows.
Boundary Adjustment Animation: Show how the boundaries shrink with each layer.
Applications of Spiral Order Traversal
Image Processing: Traversing pixels in a spiral pattern.
Game Development: Movement logic in grid-based games.
Data Visualization: Presenting multi-dimensional data in a linearized spiral format.
This comprehensive guide should make spiral order matrix traversal approachable and easy to implement. Use the provided code and explanations to tackle similar problems confidently. Click here to know more our program!