Spiral Matrix II

Problem Id: 59 Difficulty: Medium Tag: Array


Intuition

This problem is not hard to get the algorithm. But its hard to notice all the edge cases.

So we need a good start. First, it's hard to combine all the 4 situation (left, right, up, down). So we would solve it by using 4 different if condition. And move one printer (at position matrix[x][y]) to mark the values one by one.

We would need 4 variables to mark the wall, lo_x, hi_x, lo_y and hi_y. Each time we hit the wall, we need to turn. And each time we turn, one line is finished, and we need to move a wall to make sure we don't hit it for more than once.

Solution


class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        lo_x, lo_y, hi_x, hi_y = 0, 0, n - 1, n - 1
        x, y = 0, 0
        matrix = [[None] * n for _ in range(n)]
        direction = 0
        count = 1
        while True:
            if hi_x < lo_x or hi_y < lo_y:
                return matrix

            matrix[x][y] = count
            count += 1
            if direction == 0:
                if y == hi_y:
                    lo_x += 1
                    direction = 1
                    x += 1
                else:
                    y += 1
            elif direction == 1:
                if x == hi_x:
                    hi_y -= 1
                    direction = 2
                    y -= 1
                else:
                    x += 1
            elif direction == 2:
                if y == lo_y:
                    hi_x -= 1
                    direction = 3
                    x -= 1
                else:
                    y -= 1
            else:
                if x == lo_x:
                    lo_y += 1
                    direction = 0
                    y += 1
                else:
                    x -= 1