MatrixProblem 1 of 10
Spiral traversal on a Matrix
Problem Statement
Given an m x n matrix, return all elements of the matrix in spiral order (clockwise from outside to inside).
Example:
- Input:
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] - Output:
[1, 2, 3, 6, 9, 8, 7, 4, 5] - Explanation: Starting from top-left, traverse right → down → left → up, then move inward and repeat.
Approach 1: Simulation with Visited Matrix
Intuition
Simulate the spiral traversal by keeping track of visited cells. Change direction when hitting a boundary or visited cell.
Algorithm
- Create a visited matrix to track cells already traversed
- Start from (0, 0) and move in direction order: right → down → left → up
- When hitting boundary or visited cell, change to next direction
- Continue until all cells are visited
java
import java.util.*;
public class Solution {
public List<Integer> spiralOrderBrute(int[][] matrix) {
List<Integer> result = new ArrayList<>();
if (matrix.length == 0) return result;
int m = matrix.length, n = matrix[0].length;
boolean[][] visited = new boolean[m][n];
// Directions: right, down, left, up
int[] dr = {0, 1, 0, -1};
int[] dc = {1, 0, -1, 0};
int row = 0, col = 0, dir = 0;
for (int i = 0; i < m * n; i++) {
result.add(matrix[row][col]);
visited[row][col] = true;
int newRow = row + dr[dir];
int newCol = col + dc[dir];
// Check if need to change direction
if (newRow < 0 || newRow >= m || newCol < 0 || newCol >= n || visited[newRow][newCol]) {
dir = (dir + 1) % 4;
newRow = row + dr[dir];
newCol = col + dc[dir];
}
row = newRow;
col = newCol;
}
return result;
}
}Complexity Analysis
- Time Complexity: O(m*n) - Visit each cell exactly once
- Space Complexity: O(m*n) - Extra space for visited matrix
Approach 2: Layer-by-Layer (Optimal)
Intuition
Process the matrix layer by layer from outside to inside. For each layer, traverse the four boundaries: top row → right column → bottom row → left column.
Algorithm
- Maintain four boundaries: top, bottom, left, right
- For each layer:
- Traverse top row from left to right
- Traverse right column from top to bottom
- Traverse bottom row from right to left (if exists)
- Traverse left column from bottom to top (if exists)
- Shrink boundaries after each complete layer
java
import java.util.*;
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
if (matrix.length == 0) return result;
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
// Traverse top row
for (int col = left; col <= right; col++) {
result.add(matrix[top][col]);
}
top++;
// Traverse right column
for (int row = top; row <= bottom; row++) {
result.add(matrix[row][right]);
}
right--;
// Traverse bottom row (if exists)
if (top <= bottom) {
for (int col = right; col >= left; col--) {
result.add(matrix[bottom][col]);
}
bottom--;
}
// Traverse left column (if exists)
if (left <= right) {
for (int row = bottom; row >= top; row--) {
result.add(matrix[row][left]);
}
left++;
}
}
return result;
}
}Complexity Analysis
- Time Complexity: O(m*n) - Visit each cell exactly once
- Space Complexity: O(1) - Only using pointers (excluding output array)
Key Takeaways
- Boundary management is the key to solving spiral traversal efficiently
- The layer-by-layer approach avoids extra space for tracking visited cells
- Always check boundary conditions before traversing bottom row and left column to avoid duplicates
- This pattern is useful for many matrix traversal problems (anti-spiral, zigzag, etc.)
- Can be extended for anti-clockwise spiral by changing the order of traversal
- The direction-based approach with visited matrix is more intuitive but uses extra space