Dare2Solve
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.
Initialization:
Determine the number of rows (m
) and columns (n
) in the matrix.
Initialize the result list res
to store the elements in spiral order.
Initialize pointers for the current position (x
, y
) and direction (dx
, dy
). We start moving right, so dx = 1
and dy = 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 list res
.
Mark the current cell as visited (e.g., by setting it to a special value like float('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
and dy
, and negating dy
.
Move to the Next Cell:
x
, y
) based on the direction (dx
, dy
).Return the Result:
res
containing the elements in spiral order.O(m * n)
O(1)
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
int x = 0;
int y = 0;
int dx = 1;
int dy = 0;
vector<int> 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;
}
};
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
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> 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;
}
}
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;
};