Problem Statement in English

You’re given an m x n matrix. Return all elements of the matrix in spiral order.

Approach

We can solve this problem by simulating the spiral traversal of the matrix.

We can keep track of the boundaries of the matrix and move in a spiral pattern: right, down, left, and up using a direction offset array. We will also maintain a set to keep track of the visited cells to avoid revisiting them.

If we go out of bounds or hit a visited cell, we change direction and continue until all cells are visited.

And we’re done!

Solution in Python


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        seen = set()

        m = len(matrix)
        n = len(matrix[0])
        res = []

        x, y = 0, 0

        moves = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        move_index = 0

        while len(seen) < m * n:
            if (x, y) not in seen:
                res.append(matrix[x][y])
                seen.add((x, y))

            nx = x + moves[move_index][0]
            ny = y + moves[move_index][1]

            if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in seen:
                x, y = nx, ny
            else:
                move_index += 1
                move_index %= 4

        return res

Complexity

  • Time: $O(m \times n)$
    Where $m$ is the number of rows and $n$ is the number of columns in the matrix.

  • Space: $O(m \times n)$
    The space complexity is due to the seen set that stores all visited positions.

And we are done.