spiral_matrix

Solution

	
	"""
Problem:
https://leetcode.com/problems/spiral-matrix/description/

Solution:
https://www.youtube.com/watch?v=BJnMZNwUk1M

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

from typing import List


def spiral_order(matrix: List[List[int]]) -> List[int]:
    left, right = 0, len(matrix[0])
    top, bottom = 0, len(matrix)

    def done():
        if top < bottom and left < right:
            return False
        return True

    out = []
    while not done():
        for i in range(left, right):
            out.append(matrix[top][i])
        top += 1
        for i in range(top, bottom):
            out.append(matrix[i][right - 1])
        right -= 1
        if done():
            break
        for i in range(right - 1, left - 1, -1):
            out.append(matrix[bottom - 1][i])
        bottom -= 1
        for i in range(bottom - 1, top - 1, -1):
            out.append(matrix[i][left])
        left += 1
    return out

	

Tests

	
	import pytest

from publicmatt.leet.problems.spiral_matrix import spiral_order


def test_empty():
    assert spiral_order([[]]) == []


def test_single():
    assert spiral_order([[1]]) == [1]


def test_wide():
    assert spiral_order([[1, 2, 3]]) == [1, 2, 3]


def test_tall():
    assert spiral_order([[1], [2], [3]]) == [1, 2, 3]


def test_large():
    assert spiral_order([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) == [
        1,
        2,
        3,
        6,
        9,
        8,
        7,
        4,
        5,
    ]