Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Spiral Matrix

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

Example 1

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Solution

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        result = []

        R = len(matrix)
        C = len(matrix[0])
        seen = [[False for c in range(C)] for r in range(R)]

        rows = len(matrix)
        cols = len(matrix[0])
        layers = min(R//2, C//2)

        # if C == 1:
        #     for r in range(R):
        #         result.append(matrix[r][0])
        #     return result

        # if R == 1:
        #     for c in range(C):
        #         result.append(matrix[0][c])
        #     return result

        for l in range(layers+1):
            # Top
            for c in range(l, cols - l):
                add_row = l
                add_col = c
                if not seen[add_row][add_col]:
                    result.append(matrix[add_row][add_col])
                    seen[add_row][add_col] = True

            # Right Side
            for r in range(l+1, rows - l - 1):
                add_row = r
                add_col = cols - l - 1
                if not seen[add_row][add_col]:
                    result.append(matrix[add_row][add_col])
                    seen[add_row][add_col] = True

            # Bottom
            for c in range(cols - l - 1, l-1, -1):
                add_row = rows - l - 1
                add_col = c
                if not seen[add_row][add_col]:
                    result.append(matrix[add_row][add_col])
                    seen[add_row][add_col] = True

            # Left Side
            for r in range(rows - l - 2, l, -1):
                add_row = r
                add_col = l
                if not seen[add_row][add_col]:
                    result.append(matrix[add_row][add_col])
                    seen[add_row][add_col] = True
        return result


def check(expected, got):
    if len(expected) != len(got):
        return False

    for i in range(len(expected)):
        if expected[i] != got[i]:
            return False

    return True


def main():
    solution = Solution()

    expected = [1]
    got = solution.spiralOrder([[1]])
    if not check(expected, got):
        print(f"Error: expected {expected} got {got}")
    else:
        print("Correct")

    expected = [1, 2, 3, 6, 9, 8, 7, 4, 5]
    got = solution.spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
    if not check(expected, got):
        print(f"Error: expected {expected} got {got}")
    else:
        print("Correct")

    expected = [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
    got = solution.spiralOrder([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]])
    if not check(expected, got):
        print(f"Error: expected {expected} got {got}")
    else:
        print("Correct")

    expected = [3, 2]
    got = solution.spiralOrder([[3], [2]])
    if not check(expected, got):
        print(f"Error: expected {expected} got {got}")

    expected = [6, 9, 7]
    got = solution.spiralOrder([[6, 9, 7]])
    if not check(expected, got):
        print(f"Error: expected {expected} got {got}")
    else:
        print("Correct")

    expected = [2, 5, 8, -1, 0, 4]
    got = solution.spiralOrder([[2, 5, 8], [4, 0, -1]])
    if not check(expected, got):
        print(f"Error: expected {expected} got {got}")
    else:
        print("Correct")

    expected = [2, 5, 4, -1, 0, 8]
    got = solution.spiralOrder([[2, 5], [8, 4], [0, -1]])
    if not check(expected, got):
        print(f"Error: expected {expected} got {got}")
    else:
        print("Correct")

    expected = [2, 3, 4, 7, 10, 13, 16, 15, 14, 11, 8, 5, 6, 9, 12]
    got = solution.spiralOrder([[2, 3, 4], [5, 6, 7], [8, 9, 10], [11, 12, 13], [14, 15, 16]])
    if not check(expected, got):
        print(f"Error: expected {expected} got {got}")
    else:
        print("Correct")


if __name__ == "__main__":
    main()