Problem
You are given anm × n matrix. Return all elements of the matrix in spiral order, starting from the top-left corner and moving right, then down, then left, and then up repeatedly toward the center.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
matrix = [ [1,2,3], [4,5,6], [7,8,9] ]Output
[1,2,3,6,9,8,7,4,5]Solution
This problem can be solved using a Boundary Traversal approach.We maintain four boundaries:
top, bottom, left, and right. These boundaries represent the remaining portion of the matrix that has not yet been traversed.
We first traverse the top row from left to right and move
top down. Then, we traverse the right column from top to bottom and move right left.
If rows are still remaining, we traverse the bottom row from right to left and move
bottom up. If columns are still remaining, we traverse the left column from bottom to top and move left right.
We continue this process until the boundaries cross.
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
List<Integer> out = new ArrayList<>();
int top = 0;
int bottom = n - 1;
int left = 0;
int right = m - 1;
while (top <= bottom && left <= right) {
// Traverse the top row.
int j = left;
while (j <= right) {
out.add(matrix[top][j]);
j++;
}
top++;
// Traverse the right column.
int i = top;
while (i <= bottom) {
out.add(matrix[i][right]);
i++;
}
right--;
// Traverse the bottom row.
if (top <= bottom) {
j = right;
while (j >= left) {
out.add(matrix[bottom][j]);
j--;
}
bottom--;
}
// Traverse the left column.
if (left <= right) {
i = bottom;
while (top <= i) {
out.add(matrix[i][left]);
i--;
}
left++;
}
}
return out;
}
}
Complexity
Each matrix element is visited exactly once, resulting inO(n × m) time complexity, and only four boundary variables are used apart from the output list, resulting in O(1) extra space.