unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 54: Spiral Matrix

link

For a square we can define the spiral order in terms of concentric disks.

But for rectangles it can be hard.

Instead, we can find a robust, local definition:

  1. Start at (0, 0) and move rightwards.
  2. As long as we have not yet processed all matrix elements, we keep moving.
  3. If the next move would go outside matrix borders or would step into an already visited cell, turn ninety degrees clockwise and move on.

To be able to mark a visited cell, we can assign None.

Time: \mathcal{O}(m \cdot n), space: \mathcal{O}( |\text{output}| ).

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        dir_map = {
            (0, 1): (1, 0),  # right -> down
            (1, 0): (0, -1),  # down -> left
            (0, -1): (-1, 0),  # left -> up
            (-1, 0): (0, 1),  # up -> right
        }
        total = m * n
        spiral = []
        r, c = 0, 0
        curr_dir = (0, 1)  # right
        while len(spiral) < total:
            # Invariant: (r, c) is valid, new element
            spiral.append(matrix[r][c])
            matrix[r][c] = None

            dr, dc = curr_dir
            next_r, next_c = r + dr, c + dc
            if (
                (next_r < 0 or next_r > m - 1)
                or (next_c < 0 or next_c > n - 1)
                or matrix[next_r][next_c] is None
            ):
                # Change direction
                curr_dir = dir_map[curr_dir]

            dr, dc = curr_dir
            next_r, next_c = r + dr, c + dc
            r, c = next_r, next_c
        return spiral

If updating the matrix is not feasible, we can use the below two observations to skip updating:

  1. Each of the four borders of the matrix serves to bound movement in one specific direction. So, we can make boundary check specific to a direction.
  2. Second time we move rightwards, we can move one step less. That holds for other directions as well. So, on every change direction we can update the borders accordingly.
from enum import Enum


class Direction(Enum):
    Right = (0, 1)
    Down = (1, 0)
    Left = (0, -1)
    Up = (-1, 0)


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        dir_map = {
            Direction.Right: Direction.Down,
            Direction.Down: Direction.Left,
            Direction.Left: Direction.Up,
            Direction.Up: Direction.Right,
        }
        total = m * n
        row_min, row_max = 0, m - 1
        col_min, col_max = 0, n - 1
        spiral = []
        r, c = 0, 0
        curr_dir = Direction.Right
        while len(spiral) < total:
            # Invariant: (r, c) is valid, new element
            spiral.append(matrix[r][c])

            dr, dc = curr_dir.value
            next_r, next_c = r + dr, c + dc
            if (
                (curr_dir == Direction.Up and next_r < row_min)
                or (curr_dir == Direction.Down and next_r > row_max)
                or (curr_dir == Direction.Left and next_c < col_min)
                or (curr_dir == Direction.Right and next_c > col_max)
            ):
                # Change direction
                next_dir = dir_map[curr_dir]
                if curr_dir == Direction.Right:
                    col_max -= 1
                elif curr_dir == Direction.Down:
                    row_max -= 1
                elif curr_dir == Direction.Left:
                    row_min += 1
                else:
                    col_min += 1

                curr_dir = next_dir

            dr, dc = curr_dir.value
            next_r, next_c = r + dr, c + dc
            r, c = next_r, next_c
        return spiral

tanvirdotzaman

,

Leave a comment