54. Spiral Matrix

Description

Given an m x n matrix, return all elements of the matrix in spiral order.

Solutions

Solution 1: Simulation (with extra space)

This solution simulates the spiral traversal using four directions (right, down, left, up). A boolean matrix vis tracks visited cells.

Algorithm:

1. Initialize i, j, k (direction), ans (result list), and vis (visited matrix).
2. Iterate m * n times:
   • Add the current element matrix[i][j] to ans.
   • Mark matrix[i][j] as visited.
   • Try to move in the current direction (k).
   • If the next move is out of bounds or already visited, change direction (k = (k + 1) % 4).
   • Update i and j based on the new direction.

Time Complexity: O(mn) - We visit each cell once. Space Complexity: O(mn) - For the vis matrix and ans list.

Solution 2: Simulation (space-optimized)

This solution optimizes space by modifying the matrix itself to track visited cells. We add a large constant (300) to a cell after visiting it. This works because the problem states that matrix elements are in the range [-100, 100].

Algorithm:

1. Initialize i, j, k, ans.
2. Iterate m * n times:
   • Add the current element matrix[i][j] to ans.
   • Add 300 to matrix[i][j] to mark it as visited.
   • Try to move in the current direction (k).
   • If the next move is out of bounds or already visited (value > 100), change direction.
   • Update i and j.
3. Finally, subtract 300 from all cells to restore the original matrix (optional).

Time Complexity: O(m*n) - We visit each cell twice (once for traversal, once for restoration). Space Complexity: O(1) - We use constant extra space. The matrix itself is modified but restored.

Code (Python3 - Solution 1):

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        dirs = (0, 1, 0, -1, 0) # Right, Down, Left, Up
        vis = [[False] * n for _ in range(m)]
        i = j = k = 0
        ans = []
        for _ in range(m * n):
            ans.append(matrix[i][j])
            vis[i][j] = True
            x, y = i + dirs[k], j + dirs[k + 1]
            if x < 0 or x >= m or y < 0 or y >= n or vis[x][y]:
                k = (k + 1) % 4
            i += dirs[k]
            j += dirs[k + 1]
        return ans
 

Code (Python3 - Solution 2):

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        dirs = (0, 1, 0, -1, 0)
        i = j = k = 0
        ans = []
        for _ in range(m * n):
            ans.append(matrix[i][j])
            matrix[i][j] += 300
            x, y = i + dirs[k], j + dirs[k + 1]
            if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] > 100:
                k = (k + 1) % 4
            i += dirs[k]
            j += dirs[k + 1]
        for i in range(m):
            for j in range(n):
                matrix[i][j] -= 300
        return ans

(Other language implementations would follow a similar structure, adapting syntax and data structures as needed. The core logic remains the same.)