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.
1var spiralOrder = function(matrix) {
2 let result = [];
3 let top = 0, bottom = matrix.length - 1;
4 let left = 0, right = matrix[0].length - 1;
5 while (top <= bottom && left <= right) {
6 for (let i = left; i <= right; i++) result.push(matrix[top][i]);
7 top++;
8 for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
9 right--;
10 if (top <= bottom) {
11 for (let i = right; i >= left; i--) result.push(matrix[bottom][i]);
12 bottom--;
13 }
14 if (left <= right) {
15 for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
16 left++;
17 }
18 }
19 return result;
20};The JavaScript solution takes advantage of arrays and loops to traverse the matrix edges in a spiral manner. The boundary variables help to decide which part of the matrix needs to be processed next.
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.