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

O(mn)

Обходите сетку слой за слоем (спираль) или по диагоналям, сдвигая границу внутрь после каждого прохода. Та же координатная математика поворачивает сетку на 90 градусов вообще без спирали.

Сигналы

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

Шаблон

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;
}

Похоже, но не то

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

сетка до ~1e3 x 1e3 ячеек, каждая ячейка посещается ровно один раз -> O(m*n): спираль, диагональ или поворот затрагивают каждую ячейку один раз.

Изучить этот паттерн