Spiral Matrix

The problem description can be found in LeetCode.

Approach

For this problem, it is enough to follow this pattern for the directions:

1. Right.
2. Down.
3. Left.
4. Up.

Then, we can repeat the process until the are elements to check.

We just need to be careful and avoid to visit an element more than once. We could use a Set to achieve this.

from enum import Enum
from typing import List, Tuple


class Direction(Enum):
    UP = 0
    DOWN = 1
    LEFT = 2
    RIGHT = 3


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        rows, cols = len(matrix), len(matrix[0])
        n = rows * cols
        pos = Direction.RIGHT
        row = col = 0

        ans: List[int] = []
        visited = {(0, 0)}
        stack = [(0, 0)]
        while len(ans) != n:
            row, col = stack.pop()
            ans.append(matrix[row][col])

            new_row, new_col = self.get_next_position(row, col, pos)
            if (
                not self.is_valid_position(new_row, new_col, rows, cols)
                or (new_row, new_col) in visited
            ):
                pos = self.change_position(pos)
                new_row, new_col = self.get_next_position(row, col, pos)

            stack.append((new_row, new_col))
            visited.add((new_row, new_col))

        return ans

    def change_position(self, pos: Direction) -> Direction:
        if pos == Direction.UP:
            return Direction.RIGHT
        if pos == Direction.DOWN:
            return Direction.LEFT
        if pos == Direction.LEFT:
            return Direction.UP
        if pos == Direction.RIGHT:
            return Direction.DOWN

        assert False, f"unknown position `{pos}`"

    def get_next_position(self, row: int, col: int, pos: Direction) -> Tuple[int, int]:
        if pos == Direction.UP:
            return row - 1, col
        if pos == Direction.DOWN:
            return row + 1, col
        if pos == Direction.LEFT:
            return row, col - 1
        if pos == Direction.RIGHT:
            return row, col + 1

        assert False, f"unknown position `{pos}`"

    def is_valid_position(self, row: int, col: int, rows: int, cols: int) -> bool:
        return 0 <= row < rows and 0 <= col < cols

This solution would work, but it requires extra space for both the next element to pick and the visited coordinates.

However, there is a better approach that won't use any extra space. Let's derive some examples:

a  b  c  d
e  f  g  h
i  j  k  l

This would would require:

• |cols| steps right.
• |rows| - 1 steps down.
• |cols| - 1 steps left.
• |rows| - 2 steps up.
• |cols| - 2 steps right.

Moreover, we can notice that between (right, down) and (left, up) only the directions are different. So, if we group these four operations into two groups, we would end up by just having horizontal (left and right) and vertical (up and down) movements.

Solution

from typing import List


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        rows, cols = len(matrix), len(matrix[0])
        n = rows * cols
        row, col = 0, -1
        direction = 1
        ans: List[int] = []

        while len(ans) != n:
            # horizontal
            for _ in range(cols):
                col += direction
                ans.append(matrix[row][col])
            rows -= 1

            # vertical
            for _ in range(rows):
                row += direction
                ans.append(matrix[row][col])
            cols -= 1

            direction *= -1

        return ans

Complexity

• Time: $O(mn)$
• Space: $O(mn)$

Where $m$ and $n$ are the number for rows and columns of the matrix, respectively.