This approach involves simulating the spiral order by iteratively traversing matrix layers. The boundaries are adjusted after each complete traversal of a side (top, right, bottom, left). By shrinking the boundaries, we can eventually cover the entire matrix in a spiral order.
Time Complexity: O(m * n) where m is the number of rows and n is the number of columns, since each element is accessed once.
Space Complexity: O(1) additional space, excluding the space for the output array.
1import java.util.ArrayList;
2import java.util.List;
3
4public class SpiralMatrix {
5 public List<Integer> spiralOrder(int[][] matrix) {
6 List<Integer> result = new ArrayList<>();
7 int top = 0, bottom = matrix.length - 1;
8 int left = 0, right = matrix[0].length - 1;
9 while (top <= bottom && left <= right) {
10 for (int i = left; i <= right; i++) result.add(matrix[top][i]);
11 top++;
12 for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
13 right--;
14 if (top <= bottom) {
15 for (int i = right; i >= left; i--) result.add(matrix[bottom][i]);
16 bottom--;
17 }
18 if (left <= right) {
19 for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
20 left++;
21 }
22 }
23 return result;
24 }
25}In the Java solution, we manipulate the matrix boundaries similarly using `ArrayList` to maintain the spiral order result. We iterate through the outermost side while adjusting the boundary variables, ensuring we account for all matrix elements.
This approach uses recursion to divide the matrix into smaller sections. By processing the outer layer of the matrix, we can recursively call the function on the remaining submatrix. This continues until the entire matrix is covered.
Time Complexity: O(m * n) since each recursive call processes an entire layer of the matrix.
Space Complexity: O(m * n) due to the recursive call stack usage, although tail recursion may optimize this depending on the Python implementation.
1def spiralOrder(matrix):
2 result = []
3 if matrix:
4 def spiral_layer(top, bottom, left, right):
5 if top > bottom or left > right:
6 return
7 result.extend(matrix[top][i] for i in range(left, right + 1))
8 result.extend(matrix[i][right] for i in range(top + 1, bottom + 1))
9 if top < bottom:
10 result.extend(matrix[bottom][i] for i in range(right - 1, left - 1, -1))
11 if left < right:
12 result.extend(matrix[i][left] for i in range(bottom - 1, top, -1))
13 spiral_layer(top + 1, bottom - 1, left + 1, right - 1)
14 spiral_layer(0, len(matrix) - 1, 0, len(matrix[0]) - 1)
15 return resultThe Python solution defines a recursive helper function `spiral_layer`, with parameters defining the boundaries of the current submatrix. The base condition checks if the boundary indices are valid. It extracts and appends elements to the result, then recursively narrows the boundaries until they converge.