Problem of The Day: Spiral Matrix III

Problem Statement

Note:

• Need to review

Brute Force - TLE

class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:
        r, c = rStart, cStart
        res = [[r, c]]
        right = [0, 1]
        down = [1, 0]
        left = [0, -1]
        up = [-1, 0]
        n = rows * cols
        level = 0
        while n > 0:
            for _ in range(level + 1):
                r += right[0]
                c += right[1]
                if 0 <= r < rows and 0 <= c < cols:
                    res.append([r, c])

            for _ in range(level + 1):
                r += down[0]
                c += down[1]
                if 0 <= r < rows and 0 <= c < cols:
                    res.append([r, c])

            level += 1

            for _ in range(level + 1):
                r += left[0]
                c += left[1]
                if 0 <= r < rows and 0 <= c < cols:
                    res.append([r, c])

            for _ in range(level + 1):
                r += up[0]
                c += up[1]
                if 0 <= r < rows and 0 <= c < cols:
                    res.append([r, c])

            level += 1
            n -= 1

        return res

Editorial

class Solution:
    def spiralMatrixIII(
        self, rows: int, cols: int, rStart: int, cStart: int
    ) -> List[List[int]]:
        # Store all possible directions in an array.
        dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        traversed = []

        # Initial step size is 1, value of d represents the current direction.
        step = 1
        direction = 0
        while len(traversed) < rows * cols:
            # direction = 0 -> East, direction = 1 -> South
            # direction = 2 -> West, direction = 3 -> North
            for _ in range(2):
                for _ in range(step):
                    # Validate the current position
                    if (
                        rStart >= 0
                        and rStart < rows
                        and cStart >= 0
                        and cStart < cols
                    ):
                        traversed.append([rStart, cStart])
                    # Make changes to the current position.
                    rStart += dir[direction][0]
                    cStart += dir[direction][1]

                direction = (direction + 1) % 4
            step += 1
        return traversed