Обход матрицы (спираль / диагонали)

Обход матрицы (спираль / диагонали): как это работает?

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

Пройдите верхний ряд слева направо, потом опустите верхнюю границу. Этот ряд уже использован.

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

Проверяйте границы перед двумя последними проходами. Иначе единственный оставшийся ряд пройдут дважды.

Обход по диагоналям группирует клетки по сумме двух индексов. У всех клеток одной диагонали эта сумма одинакова.

Направление переворачивается на каждой следующей диагонали. Именно это и даёт зигзаг.

1. верхний ряд: 1, 2, 3Сетка три на три, обход спиралью.
2. правый столбец: 6, 9Сверху вниз, потом правая граница уходит влево.
3. нижний ряд: 8, 7Справа налево, потом нижняя граница уходит вверх.
4. левый столбец: 4Снизу вверх, потом левая граница уходит вправо.
5. центр: 5Осталась одна клетка. Четыре границы встретились.

function spiralOrder(matrix) {
    const result = [];
    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;
    while (top <= bottom && left <= right) {
        for (let c = left; c <= right; c++) result.push(matrix[top][c]);
        for (let r = top + 1; r <= bottom; r++) result.push(matrix[r][right]);
        if (top < bottom) for (let c = right - 1; c >= left; c--) result.push(matrix[bottom][c]);
        if (left < right) for (let r = bottom - 1; r > top; r--) result.push(matrix[r][left]);
        top++; bottom--; left++; right--;
    }
    return result;
}

Обход матрицы (спираль / диагонали): разбор примера

Повернуть квадратную матрицу на месте

Поверните матрицу n на n на девяносто градусов по часовой стрелке, на месте.

Выделять вторую матрицу нельзя.

Сначала транспонируйте её, меняя каждую клетку с зеркальной через диагональ.

Потом разверните каждый ряд. Эти два действия вместе и дают поворот.

function rotate(matrix) {
    const n = matrix.length;

    // transpose: j starts at i + 1, so no swap is undone
    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();

    return matrix;
}

Обход матрицы (спираль / диагонали): когда применять?

Эти формулировки в условии ведут сюда:

• •прочитать или заполнить сетку по спирали
• •обойти матрицу по диагоналям
• •повернуть матрицу на 90 градусов
• •посетить каждую ячейку в фиксированном геометрическом порядке

Обход матрицы (спираль / диагонали): с чем путают?

• Поиск в матрице (отсортированная сетка) (Matrix search (sorted grid)): Там порядок используют, чтобы пропустить большую часть сетки. Здесь посещается каждая клетка.
• Поиск слова в матрице (DFS/backtracking по сетке) (Matrix word search (grid DFS/backtracking)): Там идёт перебор с откатом и разворотами. Здесь путь задан заранее.
• Обход графа BFS / DFS (Graph BFS / DFS): Обход идёт по рёбрам из стартовой вершины. Здесь порядок задаёт геометрия.
• Преобразование массива на месте (In-place array transform): Поворот матрицы на месте это та же идея в двух измерениях. Правило про один буфер то же самое.

Обход матрицы (спираль / диагонали): частые ошибки

• Транспонируют по всей сетке

  Тогда каждый обмен отменяется своим же зеркальным. Начинайте внутренний цикл с i плюс один.

• Проходят оставшийся ряд дважды

  Единственный средний ряд читается вперёд, а потом назад. Проверяйте границы перед двумя последними проходами.

• Считают сетку квадратной

  Спираль по широкой сетке раньше исчерпывает столбцы. Границы это учитывают, фиксированное число кругов нет.

• Меняют местами индексы ряда и столбца

  Обычный порядок это сначала ряд, потом столбец. Их перестановка молча транспонирует всё.

Обход матрицы (спираль / диагонали): задачи с собеседований

• Спиральный обход матрицы: Четыре границы, сходящиеся внутрь кольцо за кольцом.
• Спиральное заполнение матрицы: Сетка в этом порядке заполняется, а не читается.
• Поворот изображения: Транспонировать, потом развернуть каждый ряд.
• Диагональный обход: Клетки группируются по сумме индексов.
• Обнуление строк и столбцов: Первый ряд и первый столбец служат пометками.
• Транспонирование матрицы: Кирпич, из которого собран поворот.
• Зигзагообразная запись: То же чередование направления, но по строке.

Обход матрицы (спираль / диагонали): сложность по времени и памяти

O(mn)

Сетка r на c даёт O(rc), потому что каждая клетка посещается один раз. Память O(1) сверх ответа.