https://leetcode.com/problems/spiral-matrix/
Given an m x n matrix, return all elements of the matrix in spiral order.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
- code
//[[1,2,3],[4,5,6],[7,8,9]]
// 0,1 -> 1,0 -> 0,-1 -> -1,0
// right (x, y+1) down (x+1, y) left (x, y-1) up(x-1, y)
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
int x = 0, y = 0;
int width = matrix[0].length;
int height = matrix.length;
int dx = 0, dy = 1;
while (res.size() < height * width){
res.add(matrix[x][y]);
matrix[x][y] = Integer.MAX_VALUE;
if (x + dx == height || x + dx < 0
|| y + dy == width || y + dy < 0
|| matrix[x+dx][y+dy] == Integer.MAX_VALUE){
int temp = dx;
dx = dy;
dy = -temp;
}
x += dx;
y += dy;
}
return res;
}
}
- code
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
rows = len(matrix)
cols = len(matrix[0])
x,y = 0,-1 #starting position
dx,dy = 0,1 #starting direction
ans = []
while len(ans) < rows* cols:
x, y = x+dx, y+dy #take a step in current direction
ans.append(matrix[x][y])
matrix[x][y] = None #Mark visited cells as None, so you don't visit them again, Alternatively you can maintain a seperate set to record visited coordinates.
if x+dx >= rows or y+dy >= cols or matrix[x+dx][y+dy] == None: #Don't visit visited cells again
dx, dy = dy, -dx #Turn 90 degree clock wise
return ans
- code
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
row_max, col_max = len(matrix), len(matrix[0])
col_min = row_min = 0
res = []
x = y = 0
direction = "right"
while len(res) < len(matrix) * len(matrix[0]):
res.append(matrix[x][y])
if direction == "right":
if y < col_max - 1: y += 1
else:
direction = "down"
row_min += 1
x += 1
elif direction == "down":
if x < row_max - 1: x += 1
else:
direction = "left"
col_max -= 1
y -= 1
elif direction == "left":
if y > col_min: y -= 1
else:
direction = "up"
row_max -= 1
x -= 1
elif direction == "up":
if x > row_min: x -= 1
else:
direction = "right"
col_min += 1
y += 1
return res