54. Spiral Matrix

Problem¶

Given a nonempty rectangular matrix, return its elements clockwise in spiral order, starting at the top-left corner.

[[1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]] -> [1, 2, 3, 6, 9, 8, 7, 4, 5]

Key trick¶

Maintain four boundaries and shrink the corresponding boundary after traversing each side.

Trap¶

After traversing the top and right sides, verify that rows or columns remain before traversing the bottom and left sides; otherwise, elements may be duplicated.

Why is it interesting?¶

It tests boundary management, traversal invariants, and handling rectangular or single-row matrices without extra storage.

Python solution¶

class Solution:
    def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
        res = []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1

        while top <= bottom and left <= right:
            # Traverse the current top edge.
            for c in range(left, right + 1):
                res.append(matrix[top][c])
            top += 1

            # Traverse the current right edge.
            for r in range(top, bottom + 1):
                res.append(matrix[r][right])
            right -= 1

            # Avoid repeating a r when no rows remain.
            if top <= bottom:
                for c in range(right, left - 1, -1):
                    res.append(matrix[bottom][c])
                bottom -= 1

            # Avoid repeating a c when no columns remain.
            if left <= right:
                for r in range(bottom, top - 1, -1):
                    res.append(matrix[r][left])
                left += 1

        return res

Time complexity is \(O(mn)\) and auxiliary space is \(O(1)\), excluding the returned list.

Comment on my solution¶

Your solution is correct for the stated nonempty-matrix constraints and has optimal \(O(mn)\) time and \(O(1)\) auxiliary space.

The direction state and repeated coordinate corrections make the boundary invariant harder to verify and more vulnerable to off-by-one errors. Traversing four explicit boundaries with conditional checks is simpler and more interview-friendly.

class Solution:
    def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
        # [[1,2,3],        ->  [1,2,3,6,9,8,7,4,5]
        #  [4,5,6],
        #  [7,8,9]]
        # [[1,2,3,4],      -> [1,2,3,4,8,12,11,10,9,5,6,7]
        #  [5,6,7,8],
        #  [9,10,11,12]]

        r, c = 0, 0
        left, top, right, bottom = 0, 0, len(matrix[0]), len(matrix)
        ans = []
        direction = "right"
        while top <= r < bottom and left <= c < right:
            if direction == "right":
                while c < right:
                    ans.append(matrix[r][c])
                    c += 1
                c -= 1
                r +=1
                direction = "down"
                top += 1
            elif direction == "down":
                while r < bottom:
                    ans.append(matrix[r][c])
                    r += 1
                r -= 1
                c -=1
                direction = "left"
                right -= 1
            elif direction == "left":
                while left <= c:
                    ans.append(matrix[r][c])
                    c -= 1
                c += 1
                r -=1
                direction = "up"
                bottom -= 1
            else:
                while top <= r:
                    ans.append(matrix[r][c])
                    r -= 1
                r += 1
                c +=1
                direction = "right"
                left += 1
        return ans