spiral_matrix

View Source

 1# @leet start
 2class Solution:
 3    def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
 4        """
 5        To calculate the clockwise spiral traversal of a matrix, we
 6        first note the directions we go in, which are right, down, left, up.
 7        Second, note that we start at the origin (0, 0).
 8
 9        We want to start by moving right, and then when we hit the end or a cell
10        we've already visited, we want to move down, then left, then up.
11
12        Note that the directions look like this:
13        right: (0, 1)
14        down: (1, 0)
15        left: (0, -1)
16        up: (-1, 0)
17
18        So when we want to transition from one direction to the other, we can
19        either define an explicit transition array and do modulo arithmetic
20        to keep going in a circle, or we can use the following formula:
21
22        `dx, dy = -dy, dx`.
23
24        So, (0, 1) -> (1, 0) -> (0, -1) -> (-1, 0) -> (0, 1).
25
26        We then collect the results of our traversal into an array.
27        """
28        m, n = len(matrix), len(matrix[0])
29        dy, dx, x, y = 0, 1, 0, 0
30
31        res = []
32
33        def inbounds(y, x):
34            return 0 <= y < m and 0 <= x < n
35
36        for _ in range(m * n):
37            res.append(matrix[y][x])
38            matrix[y][x] = "."
39
40            if not inbounds(dy + y, dx + x) or matrix[dy + y][dx + x] == ".":
41                dx, dy = -dy, dx
42
43            x += dx
44            y += dy
45
46        return res
47
48
49# @leet end
50
51
52def test():
53    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
 5        """
 6        To calculate the clockwise spiral traversal of a matrix, we
 7        first note the directions we go in, which are right, down, left, up.
 8        Second, note that we start at the origin (0, 0).
 9
10        We want to start by moving right, and then when we hit the end or a cell
11        we've already visited, we want to move down, then left, then up.
12
13        Note that the directions look like this:
14        right: (0, 1)
15        down: (1, 0)
16        left: (0, -1)
17        up: (-1, 0)
18
19        So when we want to transition from one direction to the other, we can
20        either define an explicit transition array and do modulo arithmetic
21        to keep going in a circle, or we can use the following formula:
22
23        `dx, dy = -dy, dx`.
24
25        So, (0, 1) -> (1, 0) -> (0, -1) -> (-1, 0) -> (0, 1).
26
27        We then collect the results of our traversal into an array.
28        """
29        m, n = len(matrix), len(matrix[0])
30        dy, dx, x, y = 0, 1, 0, 0
31
32        res = []
33
34        def inbounds(y, x):
35            return 0 <= y < m and 0 <= x < n
36
37        for _ in range(m * n):
38            res.append(matrix[y][x])
39            matrix[y][x] = "."
40
41            if not inbounds(dy + y, dx + x) or matrix[dy + y][dx + x] == ".":
42                dx, dy = -dy, dx
43
44            x += dx
45            y += dy
46
47        return res

def spiralOrder(self, matrix: list[list[int]]) -> list[int]: View Source

 4    def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
 5        """
 6        To calculate the clockwise spiral traversal of a matrix, we
 7        first note the directions we go in, which are right, down, left, up.
 8        Second, note that we start at the origin (0, 0).
 9
10        We want to start by moving right, and then when we hit the end or a cell
11        we've already visited, we want to move down, then left, then up.
12
13        Note that the directions look like this:
14        right: (0, 1)
15        down: (1, 0)
16        left: (0, -1)
17        up: (-1, 0)
18
19        So when we want to transition from one direction to the other, we can
20        either define an explicit transition array and do modulo arithmetic
21        to keep going in a circle, or we can use the following formula:
22
23        `dx, dy = -dy, dx`.
24
25        So, (0, 1) -> (1, 0) -> (0, -1) -> (-1, 0) -> (0, 1).
26
27        We then collect the results of our traversal into an array.
28        """
29        m, n = len(matrix), len(matrix[0])
30        dy, dx, x, y = 0, 1, 0, 0
31
32        res = []
33
34        def inbounds(y, x):
35            return 0 <= y < m and 0 <= x < n
36
37        for _ in range(m * n):
38            res.append(matrix[y][x])
39            matrix[y][x] = "."
40
41            if not inbounds(dy + y, dx + x) or matrix[dy + y][dx + x] == ".":
42                dx, dy = -dy, dx
43
44            x += dx
45            y += dy
46
47        return res

To calculate the clockwise spiral traversal of a matrix, we first note the directions we go in, which are right, down, left, up. Second, note that we start at the origin (0, 0).

We want to start by moving right, and then when we hit the end or a cell we've already visited, we want to move down, then left, then up.

Note that the directions look like this: right: (0, 1) down: (1, 0) left: (0, -1) up: (-1, 0)

So when we want to transition from one direction to the other, we can either define an explicit transition array and do modulo arithmetic to keep going in a circle, or we can use the following formula:

dx, dy = -dy, dx.

So, (0, 1) -> (1, 0) -> (0, -1) -> (-1, 0) -> (0, 1).

We then collect the results of our traversal into an array.

def test(): View Source

53def test():
54    assert 2 + 2 == 4