LC 54 & LC 59

Solution to LeetCode 54 Spiral Matrix and LeetCode 59 Spiral Matrix II.

LeetCode 54

Spiral Matrix (Medium) [link]

1] Simulation. Time complexity O(nm). Space complexity O(nm).

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]: return []

        M, N = len(matrix), len(matrix[0]) # row, col
        row1, col1, row2, col2 = 0, 0, M-1, N-1
        res = []

        while row1<=row2 and col1<=col2:
            for col in range(col1, col2+1):
                res.append(matrix[row1][col])
            for row in range(row1+1, row2+1):
                res.append(matrix[row][col2])
            if row1 < row2 and col1 < col2:
                for col in range(col2-1, col1, -1):
                    res.append(matrix[row2][col])
                for row in range(row2, row1, -1):
                    res.append(matrix[row][col1])
            row1 += 1
            row2 -= 1
            col1 += 1
            col2 -= 1
        return res

2] Creative way. Time complexity O(nm). Space complexity O(nm).

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res.extend(matrix.pop(0)) # res += matrix.pop(0)
            matrix = list(zip(*matrix))[::-1]
        return res

LeetCode 59

Spiral Matrix II (Medium) [link]

Simulation. Time complexity O(nm). Space complexity O(nm).

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        res = [[0]*n for _ in range(n)]
        candidate = [i for i in range(1, n**2+1)]
        
        row1, row2, col1, col2 = 0, n-1, 0, n-1
        while row1 <= row2 and col1 <= col2:
            for col in range(col1, col2+1):
                val = candidate.pop(0)
                res[row1][col] = val
                
            for row in range(row1+1, row2+1):
                val = candidate.pop(0)
                res[row][col2] = val
                
            if row1 < row2 and col1 < col2:
                for col in range(col2-1, col1, -1):
                    val = candidate.pop(0)
                    res[row2][col] = val
                    
                for row in range(row2, row1, -1):
                    val = candidate.pop(0)
                    res[row][col1] = val
                    
            row1 += 1
            row2 -= 1
            col1 += 1
            col2 -= 1
        return res