Spiral Matrix Traversal
Traverse an m×n matrix in spiral order: start from top-left, move right along top edge, down right edge, left along bottom edge, up left edge, then repeat inward. Classic problem testing boundary management, direction changes, and edge cases. Used in image processing, matrix manipulation, and game development.
Visualization
Interactive visualization for Spiral Matrix Traversal
Interactive visualization with step-by-step execution
Implementation
1function spiralOrder(matrix: number[][]): number[] {
2 if (!matrix.length) return [];
3
4 const result: number[] = [];
5 let top = 0, bottom = matrix.length - 1;
6 let left = 0, right = matrix[0].length - 1;
7
8 while (top <= bottom && left <= right) {
9 // Traverse right
10 for (let col = left; col <= right; col++) {
11 result.push(matrix[top][col]);
12 }
13 top++;
14
15 // Traverse down
16 for (let row = top; row <= bottom; row++) {
17 result.push(matrix[row][right]);
18 }
19 right--;
20
21 // Traverse left
22 if (top <= bottom) {
23 for (let col = right; col >= left; col--) {
24 result.push(matrix[bottom][col]);
25 }
26 bottom--;
27 }
28
29 // Traverse up
30 if (left <= right) {
31 for (let row = bottom; row >= top; row--) {
32 result.push(matrix[row][left]);
33 }
34 left++;
35 }
36 }
37
38 return result;
39}Deep Dive
Theoretical Foundation
Spiral traversal maintains four boundaries (top, bottom, left, right) that progressively shrink inward. Move in four directions cyclically: right → down → left → up. After completing each edge, shrink the corresponding boundary. Critical: check boundaries before traversing left and up to handle rectangular matrices. Time: O(m×n) - visit each element once. Space: O(1) excluding output array.
Complexity
Time
O(m×n)
O(m×n)
O(m×n)
Space
O(1)
Applications
Industry Use
Image processing (spiral scanning)
Matrix printing in spiral form
Game development (spiral tile generation)
Display patterns (LED matrices)
Spiral traversal in pathfinding
Ulam spiral (prime number visualization)
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.