Rotate Image: поворот матрицы на 90° на месте без лишней памяти

Коротко

Задача из матричного раздела Blind 75, её любят давать на скрининге: условие помещается в одну строку, а ошибиться в индексах можно десятком способов. Ниже — от формулы к двум решениям на месте, потом варианты поворота и разбор типичных ошибок. Спиральный обход, который часто идёт в паре с этой задачей, разобран в статье про Spiral Matrix.

Условие

Дана квадратная матрица n × n — «картинка». Нужно повернуть её на 90° по часовой стрелке на месте: менять элементы исходной матрицы, а не строить новую.

Вход:           Выход:
1 2 3           7 4 1
4 5 6           8 5 2
7 8 9           9 6 3

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

Формула поворота

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

• Столбец j превращается в строку j. Значит, новая строка — j.
• Чем выше элемент был в столбце, тем правее он окажется в строке. Верхний (i = 0) уезжает в последний столбец, нижний (i = n - 1) — в первый. Значит, новый столбец — n - 1 - i.

Проверим на примере: 5 стоит в (1, 1) и остаётся на месте, потому что $(1, 3 - 1 - 1) = (1, 1)$. 3 стоит в (0, 2) и переезжает в $(2, 3 - 1 - 0) = (2, 2)$ — правый нижний угол. Сходится.

Эту формулу стоит проговорить на собеседовании вслух. Из неё выводятся оба решения на месте, и с её помощью легко проверить любую строку кода.

Наивное решение: новая матрица

Если про память не думать, формула превращается в код напрямую:

def rotate_copy(matrix):
    n = len(matrix)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            result[j][n - 1 - i] = matrix[i][j]
    matrix[:] = result

Время $O(n^2)$, память $O(n^2)$. Условие «на месте» нарушено, но как первый шаг на доске это нормально: вы показали, что понимаете, куда что едет, и теперь задача — избавиться от второй матрицы.

Две детали, на которых часто спотыкаются уже здесь:

• matrix[:] = result, а не matrix = result. Второе только перепривязывает локальное имя, вызывающий код увидит старую матрицу.
• [[0] * n for _ in range(n)], а не [[0] * n] * n. Во втором случае все строки — один и тот же список:

grid = [[0] * 3] * 3
grid[0][0] = 1
print(grid)  # [[1, 0, 0], [1, 0, 0], [1, 0, 0]]

Сюда же относится питоновский однострочник:

def rotate_pythonic(matrix):
    matrix[:] = [list(row) for row in zip(*matrix[::-1])]

matrix[::-1] переворачивает порядок строк, zip(*...) собирает столбцы. Получается ровно «столбцы снизу вверх». Красиво, и для боевого кода годится, но память здесь та же $O(n^2)$. На собеседовании его можно упомянуть, а потом всё равно попросят решение без копии.

Решение 1: транспонирование и разворот строк

Поворот на 90° раскладывается на два простых отражения.

1. Транспонирование — отражение относительно главной диагонали: (i, j) → (j, i).
2. Разворот каждой строки — отражение относительно вертикальной оси: (i, j) → (i, n - 1 - j).

Применим их подряд к клетке (i, j): после первого шага она в (j, i), после второго — в (j, n - 1 - i). Это в точности формула поворота.

На примере:

Исходная        Транспонирование     Разворот строк
1 2 3           1 4 7                7 4 1
4 5 6     →     2 5 8          →     8 5 2
7 8 9           3 6 9                9 6 3

Оба шага легко сделать на месте: транспонирование — это обмены симметричных пар, разворот строки — встроенный reverse().

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]]

Ключевое место — range(i + 1, n) во внутреннем цикле. Мы обходим только клетки над диагональю, и каждая пара меняется ровно один раз. Подробнее о том, что будет без этого, — в разделе ошибок.

То же на JavaScript:

function rotate(matrix) {
  const n = matrix.length
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      ;[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]
    }
  }
  for (const row of matrix) row.reverse()
}

Шаги можно поменять местами, но тогда меняется и второе отражение. Сначала развернуть порядок строк (отражение относительно горизонтальной оси), потом транспонировать — тоже получится поворот по часовой:

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

Это ровно то, что делает однострочник с zip(*matrix[::-1]), только без копии.

Сложность. Время $O(n^2)$: каждую клетку трогаем константное число раз. Дополнительная память $O(1)$. row.reverse() работает на месте, а matrix.reverse() переставляет ссылки на строки, ничего не копируя.

Решение 2: послойный поворот по четвёркам

Второй классический способ ближе к самой геометрии поворота. Матрица состоит из вложенных колец (слоёв). При повороте каждое кольцо остаётся собой и просто прокручивается на четверть оборота. А внутри кольца элементы двигаются циклами по четыре: клетка с верхней стороны уходит на правую, с правой — на нижнюю, с нижней — на левую, с левой — на верхнюю.

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

def rotate_layers(matrix):
    n = len(matrix)
    for layer in range(n // 2):
        first, last = layer, n - 1 - layer
        for i in range(first, last):
            offset = i - first
            top = matrix[first][i]
            # левый → верх
            matrix[first][i] = matrix[last - offset][first]
            # низ → левый
            matrix[last - offset][first] = matrix[last][last - offset]
            # правый → низ
            matrix[last][last - offset] = matrix[i][last]
            # верх → правый
            matrix[i][last] = top

Разберём индексы. Слой задаётся границами first и last. Внутри слоя i идёт по верхней стороне от first до last - 1. Последнюю клетку стороны не берём: это угол, и он уже входит в четвёрку, начатую с левого верхнего угла. offset — насколько далеко мы отошли от угла. Четыре клетки одной четвёрки:

Проверьте любую пару по формуле $(i, j) \to (j, n - 1 - i)$: верхняя клетка (first, i) должна уехать в (i, n - 1 - first) = (i, last), то есть на правую сторону. Сходится.

Пример на матрице 4×4. Внешний слой — 12 клеток, это три четвёрки. Внутренний слой 2×2 — одна четвёрка.

m = [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]
rotate_layers(m)
print(m)
# [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]

Для нечётного n центральная клетка не входит ни в один слой: range(n // 2) её пропускает, и это правильно — при повороте центр стоит на месте.

Ту же идею можно записать без first, last и offset, через формулу напрямую. Четвёрка, начинающаяся в (i, j), — это (i, j), (j, n-1-i), (n-1-i, n-1-j), (n-1-j, i):

def rotate_quad(matrix):
    n = len(matrix)
    for i in range(n // 2):
        for j in range(i, n - 1 - i):
            (
                matrix[i][j],
                matrix[j][n - 1 - i],
                matrix[n - 1 - i][n - 1 - j],
                matrix[n - 1 - j][i],
            ) = (
                matrix[n - 1 - j][i],
                matrix[i][j],
                matrix[j][n - 1 - i],
                matrix[n - 1 - i][n - 1 - j],
            )

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

Сложность. Время $O(n^2)$, память $O(1)$. Каждая клетка, кроме центра, записывается ровно один раз.

Какое решение выбирать

На собеседовании почти всегда лучше первый вариант. Его легко объяснить («поворот — это два отражения»), легко доказать подстановкой и трудно сломать. Послойный стоит знать по двум причинам: интервьюер может попросить «без транспонирования», и он делает вдвое меньше записей, что иногда всплывает как вопрос «а можно ли быстрее». Асимптотика при этом та же, $O(n^2)$, — быстрее нельзя, ведь каждую клетку нужно хотя бы прочитать. Про то, почему константа не меняет $O$-оценку, есть отдельная статья.

Поворот против часовой и на 180°

Это самый частый follow-up. Хорошая новость: если вы решили задачу через отражения, новый код пишется за минуту.

Против часовой стрелки

Формула: $(i, j) \to (n - 1 - j,\; i)$. Раскладываем так же: транспонирование даёт (j, i), а затем нужно отразить по вертикали, то есть развернуть порядок строк:

def rotate_ccw(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]
    matrix.reverse()


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

Разница с поворотом по часовой — одна строка: matrix.reverse() вместо for row in matrix: row.reverse(). Удобная мнемоника: после транспонирования разворачиваем «внутри» (строки) — по часовой, «снаружи» (порядок строк) — против.

На 180°

Формула: $(i, j) \to (n - 1 - i,\; n - 1 - j)$. Транспонирование тут не нужно: это два разворота — порядка строк и каждой строки.

def rotate_180(matrix):
    matrix.reverse()
    for row in matrix:
        row.reverse()


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

Матрица как будто читается с конца. Кстати, этот вариант работает и для прямоугольной матрицы: форма при повороте на 180° не меняется.

На k четвертей

Поворот на k четвертей сводится к k % 4. Не надо крутить матрицу k раз: поворот на три четверти по часовой — это одна четверть против.

def rotate_k(matrix, k):
    k %= 4
    if k == 1:
        rotate(matrix)
    elif k == 2:
        rotate_180(matrix)
    elif k == 3:
        rotate_ccw(matrix)

В Python % с отрицательным k возвращает неотрицательный остаток, поэтому rotate_k(m, -1) корректно повернёт против часовой. В JavaScript, Java и C++ остаток от отрицательного числа отрицательный, там пишут ((k % 4) + 4) % 4.

А если матрица прямоугольная

Частый уточняющий вопрос: «Что изменится для m × n?». Поворот на 90° превращает её в n × m, а значит, на месте его не сделать — меняется сама форма. Строк становится другое количество, и у каждой строки другая длина. Честный ответ: новая матрица и формула result[j][m - 1 - i] = matrix[i][j], память $O(m \cdot n)$.

def rotate_rect(matrix):
    m, n = len(matrix), len(matrix[0])
    result = [[0] * m for _ in range(n)]
    for i in range(m):
        for j in range(n):
            result[j][m - 1 - i] = matrix[i][j]
    return result


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

Обратите внимание: в формуле стоит m - 1 - i, где m — число строк исходной матрицы. Для квадрата m = n, и разница не видна. На прямоугольнике путаница m и n сразу даёт IndexError — хороший повод проверить код именно на нём.

Типичные ошибки

Транспонирование по всей матрице

def rotate_broken(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(n):  # должно быть 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_broken(m)
print(m)  # [[3, 2, 1], [6, 5, 4], [9, 8, 7]]

Каждая пара меняется дважды: сначала при (i, j), потом при (j, i). Двойной обмен возвращает всё как было, и от поворота остаётся только разворот строк — зеркальная картинка. Самая частая ошибка в этой задаче, и её не видно на матрице 1×1, поэтому тестируйте хотя бы на 3×3.

Неверные границы слоёв

В послойном решении внутренний цикл идёт до last, не включая его. Если взять range(first, last + 1), последняя клетка верхней стороны — правый верхний угол — запустит ту же угловую четвёрку, что уже повернули с i = first. Углы повернутся дважды, и ответ будет неверным на любой матрице больше 1×1.

С внешним циклом ошибиться безопаснее: лишний слой из range(n // 2 + 1) даёт пустой внутренний диапазон и ничего не портит. Но такой код вызывает вопросы у интервьюера, поэтому пишите ровно range(n // 2) и объясняйте, почему центр не нужен.

Порядок присваиваний в четвёрке

С временной переменной двигаться надо против направления поворота: сохранили верх, на место верха поставили левый, на место левого — нижний и так далее. Тогда каждое значение перезаписывается только после того, как его уже скопировали. Если пойти по направлению поворота и после top = верх сразу записать правый = top, старое значение правой клетки пропадёт раньше, чем его успеют перенести вниз.

Перепривязка вместо изменения

matrix = [...] внутри функции не меняет переданную матрицу. Нужно matrix[:] = [...] или работа по индексам. На LeetCode такая ошибка выглядит как «код ничего не сделал», хотя внутри функции результат правильный.

Перепутанные стороны

Поворот по часовой и против часовой отличаются одной строкой, и их легко спутать. Защита простая: держите в голове, что после поворота по часовой первая строка — это первый столбец снизу вверх. Для [[1, 2], [3, 4]] правильный ответ начинается с 3, 1.

Связанные задачи

Приёмы из Rotate Image всплывают и в других задачах.

• Determine Whether Matrix Can Be Obtained By Rotation (LeetCode 1886). Нужно проверить, совпадает ли mat с target при каком-то повороте. Прямое решение — четыре раза повернуть и сравнить:

def find_rotation(mat, target):
    for _ in range(4):
        if mat == target:
            return True
        mat = [list(row) for row in zip(*mat[::-1])]
    return False


print(find_rotation([[0, 1], [1, 0]], [[1, 0], [0, 1]]))  # True
print(find_rotation([[0, 1], [1, 1]], [[1, 0], [0, 1]]))  # False

Можно и без копий: пройти матрицу один раз и для каждой клетки проверить четыре формулы сразу — target[i][j], target[j][n-1-i], target[n-1-i][n-1-j], target[n-1-j][i]. Это хорошая проверка, что вы помните формулы, а не только трюк с транспонированием.

• Spiral Matrix (LeetCode 54). Тот же «послойный» взгляд на матрицу: кольцо за кольцом, с аккуратными границами first и last. Разбор — в статье про спиральный обход.
• Set Matrix Zeroes (LeetCode 73). Ещё одна задача на «на месте» в матрице, где хитрость в том, чтобы использовать саму матрицу как дополнительную память.

Если готовитесь по спискам задач, Rotate Image входит в Blind 75 и большинство подборок «топ задач на массивы». Что ещё стоит решить из этого раздела, собрано в обзоре задач на массивы.

Как рассказывать на собеседовании

Удачный порядок ответа укладывается в пять-семь минут:

1. Выписать пример 3×3 и заметить, что первая строка ответа — первый столбец снизу вверх.
2. Вывести формулу $(i, j) \to (j, n - 1 - i)$ и назвать решение с копией — $O(n^2)$ памяти.
3. Предложить разложение на транспонирование и разворот строк, проверить подстановкой.
4. Написать код, явно проговорив range(i + 1, n).
5. Прогнать на 3×3 и на 1×1, назвать сложность $O(n^2)$ и $O(1)$.
6. Если спросят — показать против часовой (одна строка), 180° и почему прямоугольник на месте не повернуть.

Послойный вариант держите в запасе: он нужен, если интервьюер прямо попросит «без транспонирования» или спросит, как уменьшить число записей.