🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires us to traverse a 2D matrix in a spiral order and return the elements in that order. Spiral order traversal means moving in a specific sequence: starting from the top-left corner, we move right across the top row, then down the rightmost column, then left across the bottom row, and then up the leftmost column. This process repeats for the inner layers of the matrix until all elements have been visited.
Approach
- Initialization:
- Determine the number of rows (
m
) and columns (n
) in the matrix. - Initialize the result listres
to store the elements in spiral order. - Initialize pointers for the current position (x
,y
) and direction (dx
,dy
). We start moving right, sodx = 1
anddy = 0
. - Traverse the Matrix:
- Loop through each cell in the matrix, based on the total number of elements (
m * n
). - For each cell: - Append the current cell's value to the result listres
. - Mark the current cell as visited (e.g., by setting it to a special value likefloat('inf')
which is out of the valid range for matrix elements). - Change Direction:
- Check if the next cell (based on the current direction) is within bounds and not visited.
- If the next cell is out of bounds or already visited, change the direction by rotating it clockwise. This is done by swapping
dx
anddy
, and negatingdy
. - Move to the Next Cell:
- Update the current position (
x
,y
) based on the direction (dx
,dy
). - Return the Result:
- Once all cells are visited, return the result list
res
containing the elements in spiral order.
Complexity
Time Complexity:
O(m * n)
- We visit each element in the matrix exactly once, so the time complexity is proportional to the number of elements in the matrix.
Space Complexity:
O(1)
- We use a fixed amount of extra space (excluding the input and output) for the pointers and directions. The result list is not considered extra space for complexity analysis as it is required by the problem statement.
Code
C++
class Solution {
public:
vector spiralOrder(vector>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
int x = 0;
int y = 0;
int dx = 1;
int dy = 0;
vector res;
for (int i = 0; i < rows * cols; ++i) {
res.push_back(matrix[y][x]);
matrix[y][x] = -101;
if (!(0 <= x + dx && x + dx < cols && 0 <= y + dy && y + dy < rows)
|| matrix[y + dy][x + dx] == -101) {
int temp = dx;
dx = -dy;
dy = temp;
}
x += dx;
y += dy;
}
return res;
}
};
Python
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix or not matrix[0]:
return []
rows, cols = len(matrix), len(matrix[0])
result = []
x, y = 0, 0
dx, dy = 1, 0
for _ in range(rows * cols):
result.append(matrix[y][x])
matrix[y][x] = float('inf')
if not (0 <= x + dx < cols and 0 <= y + dy < rows) or matrix[y + dy][x + dx] == float('inf'):
dx, dy = -dy, dx
x += dx
y += dy
return result
Java
class Solution {
public List spiralOrder(int[][] matrix) {
List res = new ArrayList<>();
if (matrix == null || matrix.length == 0) return res;
int rows = matrix.length;
int cols = matrix[0].length;
int x = 0, y = 0, dx = 1, dy = 0;
int totalElements = rows * cols;
for (int i = 0; i < totalElements; i++) {
res.add(matrix[y][x]);
matrix[y][x] = Integer.MIN_VALUE;
if (!(0 <= x + dx && x + dx < cols && 0 <= y + dy && y + dy < rows)
|| matrix[y + dy][x + dx] == Integer.MIN_VALUE) {
int temp = dx;
dx = -dy;
dy = temp;
}
x += dx;
y += dy;
}
return res;
}
}
JavaScript
var spiralOrder = function(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
let x = 0;
let y = 0;
let dx = 1;
let dy = 0;
const res = [];
for (let i = 0; i < rows * cols; i++) {
res.push(matrix[y][x]);
matrix[y][x] = ".";
if (!(0 <= x + dx && x + dx < cols && 0 <= y + dy && y + dy < rows)
|| matrix[y+dy][x+dx] === ".") {
[dx, dy] = [-dy, dx];
}
x += dx;
y += dy;
}
return res;
};