Spiral Matrix

TARGET DECK: Leetcode FILE TAGS: Medium

---

Intuition

• This question requires banging your head against the wall until you get it.
• Pay really close attention to the boundary condition, making sure to go down by one column or row, and keeping in mind that python uses from [0,N) (Not including N).

Complexity

Runtime

$O(M\times N)$, since you traverse through every cell only once.

Space

$O(M\times N)$ to store the result which makes up all the cells.

Code

Checking only Length

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        size = m * n
        col_start = 0
        row_start = 0
        col_end = n - 1
        row_end = m - 1
        res = []
 
        while len(res) < size:
            # right
            for c in range(col_start, col_end + 1):
                res.append(matrix[row_start][c])
 
            # down
            for r in range(row_start + 1, row_end + 1):
                res.append(matrix[r][col_end])
            
            if len(res) < size:
                # left
                for c in range(col_end - 1, col_start - 1, -1):
                    res.append(matrix[row_end][c])
            
                # up
                for r in range(row_end - 1, row_start, -1):
                    res.append(matrix[r][col_start])
 
            row_start += 1
            row_end -= 1
            col_start += 1
            col_end -= 1
        
        return res

Checking Boundary

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        row_start = 0
        row_end = m
 
        col_start = 0
        col_end = n
        res = []
 
        while row_start < row_end and col_start < col_end:
            for i in range(col_start, col_end):
                res.append(matrix[row_start][i])
 
            for i in range(row_start + 1, row_end):
                res.append(matrix[i][col_end - 1])
 
            col_end -= 1
            
            if row_start < row_end - 1:
                for i in range(col_end - 1, col_start - 1, -1):
                    res.append(matrix[row_end - 1][i])
 
            row_end -= 1
 
            if col_start < col_end:
                for i in range(row_end - 1, row_start, -1):
                    res.append(matrix[i][col_start])
                    
            row_start += 1
            col_start += 1            
            
        
        return res

Notes

Cards

START Basic Front: Spiral Matrix Back: Visualize with one less row or column each time, and use the length of the resultant array to track progress.

END

---

References

• Spiral Matrix