54.Spiral_Matrix(Medium).md

54. Spiral Matrix (Medium)

Date and Time: Jul 14, 2024, 12:55 (EST)

Link: https://leetcode.com/problems/spiral-matrix/

Question:

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

KeyPoints:

We just repeat four directions moving: left -> right, top -> bottom, right -> left, bottom -> top. So we use four pointers l, r, t, b to indicate these four boundaries.

Everytime after we first process l->r and t->b, we should go opposite of these directions only if t <= b and l <= r. In example 2, if we process the 2nd row from l->r, t is now 2 and b = 1, we can't go r->l again, which will add redundant 6 to ans[].

My Solution:

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # l, r, t, b to indicate four boundaries
        # Repeat l->r, t->b, r->l, b->t until l == r or t == b
        # TC: O(m*n), SC: O(1)
        rows, cols = len(matrix), len(matrix[0])
        l, r, t, b = 0, cols-1, 0, rows-1
        ans = []
        while l <= r and t <= b:
            # l->r, move t downward
            for i in range(l, r+1):
                ans.append(matrix[t][i])
            t += 1
            # t->b, move r to the left
            for i in range(t, b+1):
                ans.append(matrix[i][r])
            r -= 1
            # Processing opposite directions from l->r and t->b
            # They are only valid to go when t <= b and l <= r
            # Otherwise, don't run if they are out of bound
            # r->l, move b upward
            if t <= b:
                for i in range(r, l-1, -1):
                    ans.append(matrix[b][i])
                b -= 1
            # b->t, move l to the right
            if l <= r:
                for i in range(b, t-1, -1):
                    ans.append(matrix[i][l])
                l += 1
        return ans

Time Complexity: $O(m * n)$
Space Complexity: $O(m * n)$