LeetCode #54: Spiral Matrix

LeetCode Solutions

https://leetcode.com/problems/spiral-matrix/

The problem requires us to return a list of integers in the order of the elements visited in a clockwise spiral order from a given matrix. We can solve this by traversing the matrix in a spiral order by dividing the matrix into four directions – left to right, top to bottom, right to left, and bottom to top. We keep track of the direction of traversal and stop traversing once we reach the last element of the matrix.

  1. Initialize four variables left, right, up, and down to represent the boundaries of our matrix. left and up are initially set to 0, and right and down are set to the last column index and the last row index respectively.
  2. Create an empty list res to store the elements of the matrix in a spiral order.
  3. While the length of res is less than the total number of elements in the matrix, do the following:
    • Traverse from left to right along the up row and add each element to res.
    • Traverse from up + 1 to down along the right column and add each element to res.
    • Traverse from right - 1 to left along the down row only if up and down are not the same, and add each element to res.
    • Traverse from down - 1 to up + 1 along the left column only if left and right are not the same, and add each element to res.
    • Update the boundaries by incrementing left and up, and decrementing right and down.
  4. Return res which now contains the elements of the matrix in a clockwise spiral order.

Here’s the solution code:

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        left = 0
        rows = len(matrix)
        columns = len(matrix[0])
        right = columns-1
        up = 0
        down = rows-1
        res = []
        while len(res) < rows*columns:
            for col in range(left, right+1):
                res.append(matrix[up][col])

            for row in range(up+1, down+1):
                res.append(matrix[row][right])

            if up != down:
                for col in range(right-1, left-1, -1):
                    res.append(matrix[down][col])

            if left != right:
                for row in range(down-1, up, -1):
                    res.append(matrix[row][left])
            left+=1
            right-=1
            up+=1
            down-=1
            
        return res

Time and Space Complexity

Time complexity: O(m*n) where m and n are the dimensions of the matrix, as we need to visit every element in the matrix.

Space complexity: O(m*n) as we create a list to store the elements of the matrix in a spiral order.