Spiral Matrix: обход матрицы по спирали без ошибок на краях

Коротко

Придумывать тут нечего: идти надо ровно туда, куда сказано в условии. Вся сложность в том, чтобы не взять клетку дважды, когда от матрицы остаётся одна строка или один столбец.

• На собеседовании пишите четыре границы: их проще всего объяснить через инвариант.
• Без двух проверок код проходит все квадратные матрицы и падает на части прямоугольных.
• После кода прогоните руками 1×3, 3×1 и 3×4: этого хватает, чтобы поймать типичный баг.

Условие

Дана матрица из m строк и n столбцов. Верните все элементы в порядке обхода по спирали: вправо по верхней строке, вниз по правому столбцу, влево по нижней строке, вверх по левому столбцу, и так далее внутрь.

 1   2   3   4
 5   6   7   8
 9  10  11  12

Ответ: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Обратите внимание на форму: матрица не квадратная. Для этой задачи важнее всего именно прямоугольные примеры, и дальше будет понятно почему.

Подход 1. Симуляция с вектором направления

Самое прямолинейное решение повторяет то, как вы обводите спираль карандашом. Идём вперёд, пока можем. Упёрлись в стену или в уже пройденную клетку — поворачиваем направо.

def spiral_seen(matrix):
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    res = []
    r, c = 0, 0
    dr, dc = 0, 1  # стартуем вправо

    for _ in range(rows * cols):
        res.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dr, c + dc
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            dr, dc = dc, -dr  # поворот по часовой
            nr, nc = r + dr, c + dc
        r, c = nr, nc

    return res

Поворот dr, dc = dc, -dr стоит запомнить: он даёт цепочку вправо (0, 1) → вниз (1, 0) → влево (0, -1) → вверх (-1, 0). Массив из четырёх направлений тоже подойдёт, просто выйдет на пару строк длиннее.

Сильная сторона этого решения в том, что форма матрицы ему безразлична. Цикл делает ровно rows * cols шагов, поэтому лишних элементов взять неоткуда. Одна строка, один столбец, одна клетка работают без отдельных веток.

Слабая сторона — $O(m \cdot n)$ дополнительной памяти на seen. Собеседующий почти наверняка спросит, можно ли без неё.

Частый ответ: «помечу посещённые прямо в матрице». Так можно, но с двумя оговорками. Вы портите входные данные, а значение-метка не должно совпасть с реальным элементом. 0 как метка не годится, если нули допустимы в матрице. Скажите об этом вслух, прежде чем так делать.

Подход 2. Четыре границы

Заведём четыре переменные: top, bottom, left, right. Они задают прямоугольник ещё не обойдённых клеток, обе границы включительно. Это и есть инвариант, на котором держится всё решение:

Необойдённые клетки — это ровно строки top..bottom и столбцы left..right.

Каждый проход забирает одну сторону прямоугольника и сдвигает соответствующую границу внутрь. Когда прямоугольник опустел, работа закончена.

def spiral_order(matrix):
    res = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while top <= bottom and left <= right:
        for j in range(left, right + 1):  # верхняя строка →
            res.append(matrix[top][j])
        top += 1

        for i in range(top, bottom + 1):  # правый столбец ↓
            res.append(matrix[i][right])
        right -= 1

        if top <= bottom:  # строка ещё осталась?
            for j in range(right, left - 1, -1):  # нижняя строка ←
                res.append(matrix[bottom][j])
            bottom -= 1

        if left <= right:  # столбец ещё остался?
            for i in range(bottom, top - 1, -1):  # левый столбец ↑
                res.append(matrix[i][left])
            left += 1

    return res

Разбор на матрице 3×4

Начинаем с top=0, bottom=2, left=0, right=3.

Самая важная строка таблицы — «Нижняя строка: пропуск». К этому моменту top=2 > bottom=1: строк не осталось. Без проверки цикл взял бы matrix[1][1], то есть шестёрку, второй раз.

Почему проверок две и именно здесь

Посмотрите, по чему идёт каждый цикл. Проход по столбцу перебирает строки top..bottom, поэтому при top > bottom он пуст сам собой. Проход по строке перебирает столбцы left..right и ничего не знает о том, сомкнулись ли top и bottom.

Отсюда правило: цикл защищён от выхода за свою ось, но не за чужую.

• Верхнюю строку охраняет условие while.
• Правый столбец перебирает top..bottom, а top только что сдвинулся. Если строк не осталось, цикл пуст. Столбец right ещё существует: его проверил while.
• Нижняя строка перебирает столбцы, а top уже изменился. Нужна проверка top <= bottom.
• Левый столбец перебирает строки, а right уже изменился. Нужна проверка left <= right.

Теперь эти две строки не придётся заучивать: их можно вывести прямо у доски.

Как это ломается

Убрали обе проверки

Самая частая ошибка, и она коварна. Вот что выдаёт код без if перед двумя последними проходами:

Я прогнал такой код на всех размерах до 20×20. Все квадратные матрицы проходят, и это понятно: от квадрата в конце остаётся не больше одной клетки. Прямоугольные ломаются выборочно. Падают те, где в центре остаётся строка хотя бы из двух клеток или столбец хотя бы из трёх.

Поэтому 3×4 падает, а 4×3 проходит. В 4×3 в центре столбец из двух клеток, и первые два прохода забирают его целиком. Проверить такое на одном прямоугольном примере недостаточно: можно случайно выбрать удачный.

Примеры в условии задачи на сайте — 3×3 и 2×2, и эту ошибку они не покажут. Прямоугольники придётся проверять самостоятельно.

Проверки к тому же отвечают за разное:

• без top <= bottom ломаются широкие формы: 1×2, 3×4, 5×6;
• без left <= right ломаются высокие: 3×1, 5×3, 8×5.

Кольца с полуоткрытыми отрезками

Другой популярный способ: каждая сторона идёт от угла до следующего угла, не включая его, а границы сдвигаются сразу все четыре, в конце круга.

def spiral_rings_broken(matrix):
    res = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while top <= bottom and left <= right:
        for j in range(left, right):
            res.append(matrix[top][j])
        for i in range(top, bottom):
            res.append(matrix[i][right])
        for j in range(right, left, -1):
            res.append(matrix[bottom][j])
        for i in range(bottom, top, -1):
            res.append(matrix[i][left])
        top, bottom = top + 1, bottom - 1
        left, right = left + 1, right - 1

    return res

На 2×2 и 3×4 всё хорошо, зато [[7]] даёт пустой список, 3×3 теряет центр, а 1×3 выдаёт [1, 2, 3, 2]. Вырожденное кольцо, где top == bottom или left == right, здесь надо обрабатывать отдельно, в начале цикла:

        if top == bottom:
            res.extend(matrix[top][left:right + 1])
            break
        if left == right:
            res.extend(matrix[i][left] for i in range(top, bottom + 1))
            break

С этими двумя ветками код становится верным. Подход нормальный, просто веток в нём столько же, сколько проверок в основном решении, а строк больше.

Обрезка результата

Иногда баг чинят так: return res[:rows * cols]. Лишние элементы всегда оказываются в самом конце, поэтому это действительно работает. Но собеседующий спросит, откуда взялись лишние, и ответ «не знаю, но обрезал» сыграет против вас. Лучше честно поставить проверки.

Мелочи, которые тоже встречаются

• Пустая матрица. matrix[0] на [] даёт IndexError. В ограничениях задачи такого нет, но спросите. Если допускается, в начале функции: if not matrix or not matrix[0]: return [].
• Перепутанные размеры. cols = len(matrix) вместо len(matrix[0]) на квадрате незаметно, а на прямоугольнике приводит к выходу за границы или к потере клеток.
• Индексы в обратном цикле. range(right, left, -1) вместо range(right, left - 1, -1) молча теряет последнюю клетку. Третий аргумент не сдвигает границу: конец диапазона остаётся невключённым и при обратном шаге.

Подход 3. Вектор без seen

Вектор направления можно оставить и избавиться от дополнительной памяти. Заметим, что длина прохода уменьшается предсказуемо. На матрице 3×4 проходы имеют длины 4, 2, 3, 1, 2, а следующая длина равна 0, это и есть конец.

Горизонтальные и вертикальные длины живут каждая в своём счётчике и уменьшаются на единицу после каждого прохода по своей оси.

def spiral_steps(matrix):
    res = []
    steps = [len(matrix[0]), len(matrix) - 1]  # по горизонтали, по вертикали
    r, c = 0, -1  # на клетку левее старта
    dr, dc = 0, 1
    axis = 0

    while steps[axis] > 0:
        for _ in range(steps[axis]):
            r += dr
            c += dc
            res.append(matrix[r][c])
        steps[axis] -= 1
        dr, dc = dc, -dr
        axis = 1 - axis

    return res

Здесь нет ни одной проверки формы, и граничные случаи исчезают сами. Для 1×3 счётчики равны [3, 0]: прошли три клетки вправо, вертикальный счётчик ноль, выход. Для 3×1 счётчики [1, 2]: одна клетка, две вниз, горизонтальный счётчик ноль, выход.

Цена — код труднее вывести с нуля под давлением, особенно старт с c = -1 и rows - 1 во втором счётчике. Если вы не напишете его уверенно, не рискуйте.

Что выбрать

Практический совет: начинайте с четырёх границ и сразу проговаривайте инвариант. Если чувствуете, что запутались и время уходит, рабочий вариант с seen лучше незаконченного оптимального. Память можно обсудить потом.

Смена направления хорошо показывает разницу. Чтобы пойти против часовой стрелки из левого верхнего угла, в первом решении меняются две строки: стартовое dr, dc = 1, 0 и поворот dr, dc = -dc, dr. В четырёх границах придётся переставлять все проходы и заново выводить, какие из них нуждаются в проверке.

Как проверить себя

Руками на собеседовании хватит трёх форм: 1×3, 3×1, 3×4. Дома можно сделать надёжнее и прогнать решение против простого эталона на всех небольших размерах:

def stress(solution, max_size=8):
    for rows in range(1, max_size + 1):
        for cols in range(1, max_size + 1):
            matrix = [
                [i * cols + j + 1 for j in range(cols)]
                for i in range(rows)
            ]
            actual = solution(matrix)
            expected = spiral_seen(matrix)
            assert actual == expected, f'{rows}×{cols}: {actual}'
    print('ok')


stress(spiral_order)  # ok
stress(spiral_steps)  # ok

Версия без проверок вылетает сразу с понятным сообщением: AssertionError: 1×2: [1, 2, 1].

Числа в матрице разные намеренно: так повтор виден сразу. На матрице из одинаковых значений дубль заметен только по длине ответа. Про поиск таких ошибок без запуска кода есть отдельная статья: отладка на собеседовании.

Сложность

Каждая клетка попадает в ответ ровно один раз, поэтому время $O(m \cdot n)$. Быстрее не получится: все элементы всё равно надо вывести.

Дополнительная память у границ и счётчика шагов $O(1)$: сам ответ в неё обычно не засчитывают, потому что его вернуть надо в любом случае. У варианта с seen она $O(m \cdot n)$. Если такие оценки пока даются с трудом, начните с нотации Big O.

Родственные задачи

Генерация спирали (LeetCode 59)

Обратная задача: дано n, заполнить квадрат числами от 1 до $n^2$ по спирали. Каркас тот же, только чтение заменено записью.

def generate_matrix(n):
    matrix = [[0] * n for _ in range(n)]
    top, bottom, left, right = 0, n - 1, 0, n - 1
    value = 1

    while top <= bottom and left <= right:
        for j in range(left, right + 1):
            matrix[top][j] = value
            value += 1
        top += 1
        for i in range(top, bottom + 1):
            matrix[i][right] = value
            value += 1
        right -= 1
        for j in range(right, left - 1, -1):
            matrix[bottom][j] = value
            value += 1
        bottom -= 1
        for i in range(bottom, top - 1, -1):
            matrix[i][left] = value
            value += 1
        left += 1

    return matrix


print(generate_matrix(3))  # [[1, 2, 3], [8, 9, 4], [7, 6, 5]]

Проверок здесь нет сознательно: от квадрата не остаётся вытянутого хвоста, как мы выяснили выше. На произвольном прямоугольнике этот код уже нельзя использовать без них.

Здесь есть своя ловушка: [[0] * n] * n. Это n ссылок на один и тот же список, и после m[0][0] = 1 единица появится в первом столбце каждой строки.

Если размеры прямоугольные, проще взять вектор из первого подхода. Массив seen там не понадобится: роль метки играет сама матрица, потому что ноль значит «клетка пуста», а значения начинаются с единицы. Условие поворота превращается в or matrix[nr][nc].

Поворот на 90° (LeetCode 48)

Дана квадратная матрица, повернуть её по часовой стрелке на месте. Решение в два шага: транспонировать и развернуть каждую строку.

def rotate(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()


m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate(m)
print(m)  # [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Почему это работает: клетка (i, j) после транспонирования становится (j, i), а после разворота строки — (j, n - 1 - i). Это и есть формула поворота по часовой.

Здесь тоже две типичные ошибки:

• j от 0, а не от i + 1. Каждая пара меняется дважды, и транспонирование возвращает матрицу в исходный вид. Код отрабатывает без ошибок, но матрица не транспонирована.
• matrix = ... внутри функции. Это перепривязка локального имени, вызывающий код поворота не увидит. На месте значит менять элементы, а не имя.

Прямоугольную матрицу на месте так не повернуть: у результата другие размеры. Нужна копия:

def rotate_cw(matrix):
    return [list(row) for row in zip(*matrix[::-1])]


def rotate_ccw(matrix):
    return [list(row) for row in zip(*matrix)][::-1]


print(rotate_cw([[1, 2, 3], [4, 5, 6]]))  # [[4, 1], [5, 2], [6, 3]]
print(rotate_ccw([[1, 2, 3], [4, 5, 6]]))  # [[3, 6], [2, 5], [1, 4]]

Вторая классическая реализация поворота обходит матрицу кольцами и циклически меняет четыре клетки. Памяти тоже $O(1)$, но индексы вроде matrix[n - 1 - j][i] гораздо легче перепутать.

Спираль через поворот

Поворот даёт и самый короткий спиральный обход: забираем верхнюю строку, а остаток поворачиваем против часовой, чтобы следующая сторона оказалась сверху.

def spiral_pop(matrix):
    rest = list(matrix)
    res = []
    while rest:
        res.extend(rest.pop(0))
        rest = list(zip(*rest))[::-1]
    return res

Прекрасно читается и не имеет граничных случаев. Но каждый поворот копирует весь остаток, поэтому время $O(m \cdot n \cdot \min(m, n))$, а память $O(m \cdot n)$. Для квадрата это $O(n^3)$. Как второе решение на доске хорошо, как основное — спорно.

Спираль из произвольной точки (LeetCode 885)

Старт в заданной клетке, идём наружу, клетки за границей пропускаем. Границы здесь бесполезны, потому что спираль выходит за пределы матрицы. Зато шаблон длин простой: 1, 1, 2, 2, 3, 3 и так далее.

def spiral_from(rows, cols, r, c):
    res = [[r, c]]
    dr, dc = 0, 1
    length = 1

    while len(res) < rows * cols:
        for _ in range(2):
            for _ in range(length):
                r += dr
                c += dc
                if 0 <= r < rows and 0 <= c < cols:
                    res.append([r, c])
            dr, dc = dc, -dr
        length += 1

    return res


print(spiral_from(1, 4, 0, 0))  # [[0, 0], [0, 1], [0, 2], [0, 3]]

Это тот же приём, что в подходе 3, только длины растут, а не убывают. Ещё один вариант на ту же тему — LeetCode 2326: заполнить матрицу значениями из связного списка.

Другие задачи на матрицы из того же круга: Set Matrix Zeroes (LeetCode 73) и поиск слова в сетке. Вместе со Spiral Matrix и Rotate Image они составляют матричный раздел списка Blind 75. Что ещё стоит решить из массивов, разобрано в обзоре задач на массивы.

На собеседовании

Задача проверяет не знание алгоритма. Её смотрят, чтобы понять, как вы работаете с деталями и находите собственные ошибки. Рабочий порядок действий такой:

1. Уточните условие. Матрица может быть прямоугольной? Может быть пустой? Можно ли менять входные данные?
2. Назовите инвариант. «Держу прямоугольник необойдённых клеток и каждый проход срезаю одну его сторону».
3. Напишите четыре прохода и вслух объясните, зачем нужны две проверки. Это лучший сигнал, чем сам код.
4. Прогоните руками 1×3, 3×1 и 3×4. Квадратный пример баг не покажет.
5. Назовите сложность и уточните, что ответ в память не засчитан.

Частые продолжения: обойти против часовой стрелки, начать из центра, заполнить матрицу вместо чтения, повернуть матрицу. Первые два особенно хорошо показывают, понимаете ли вы решение или помните его наизусть. Как устроен сам формат такой задачи с кодом в реальном времени, разобрано в статье про лайвкодинг.