Паттерн: Матрица

Признак в условии

• двумерная сетка, обход по спирали, поворот, транспонирование
• «обнули строку и столбец», «поверни на месте»
• координаты и границы важнее алгоритма

Идея

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

Шаблон

let top = 0, bottom = rows - 1, left = 0, right = cols - 1;
while (top <= bottom && left <= right) {
  for (let c = left; c <= right; c++) out.push(m[top][c]);
  top++;
  for (let r = top; r <= bottom; r++) out.push(m[r][right]);
  right--;
  if (top <= bottom) {                 // перепроверка обязательна
    for (let c = right; c >= left; c--) out.push(m[bottom][c]);
    bottom--;
  }
  if (left <= right) {
    for (let r = bottom; r >= top; r--) out.push(m[r][left]);
    left++;
  }
}

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

const visit = (r, c) => {
  if (r < 0 || c < 0 || r >= rows || c >= cols) return;
  ...
};

Сложность

Обычно O(rows × cols) времени. Память O(1), если работаем на месте.

Частые ошибки

• нет повторной проверки границ перед третьей и четвёртой сторонами: в матрице из одной строки элементы задваиваются
• изменение матрицы по ходу портит ещё не просмотренные клетки (обнуление нулями)
• matrix[0] без проверки на пустую матрицу
• строки, созданные через Array(n).fill([]), оказываются одной и той же ссылкой

Мнемоника

«Четыре границы, каждая сдвигается ровно один раз»

Не путать с

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

Задачи на этот паттерн

• обход матрицы по спирали
• обнуление строк и столбцов

Суть

Матрица в JS это массив массивов grid[r][c]: r строка, c столбец. Задачи бывают трёх видов: аккуратная работа с индексами (поворот, спираль), поиск с использованием сортировки, и сетка как граф (острова, лабиринт).

Как распознать по условию

• «повернуть», «транспонировать», «по спирали», «по диагоналям» → индексы и границы;
• «строки и столбцы отсортированы» → поиск из угла или бинпоиск;
• «острова», «лабиринт», «заливка», «гниющие апельсины» → BFS / DFS по клеткам;
• «обнулить строки и столбцы» → метки в первой строке и столбце.

Создание без ловушки

const grid = Array.from({ length: R }, () => new Array(C).fill(0));
// НЕ new Array(R).fill(new Array(C).fill(0)): одна строка на всех

Соседи и границы

const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (const [dr, dc] of DIRS) {
  const nr = r + dr, nc = c + dc;
  if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
  // ...
}

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

function rotate(a) {
  const n = a.length;
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j < n; j++)
      [a[i][j], a[j][i]] = [a[j][i], a[i][j]]; // транспонирование
  for (const row of a) row.reverse();           // разворот строк
}

Спираль

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

Поиск в отсортированной матрице

Если строки и столбцы отсортированы, старт из правого верхнего угла: больше x, влево; меньше, вниз. O(m + n). Если строки продолжают друг друга, это один отсортированный массив: бинпоиск по индексу i, где r = Math.floor(i / n), c = i % n, O(log(m · n)).

Сложность

Полный обход O(R · C). Поворот и спираль O(n²) или O(R · C), доп. память O(1) (кроме ответа).

Ловушки

• fill с массивом: общая строка.
• Путать grid[x][y] и grid[r][c]: договорись, что первое это строка.
• Пустая матрица [] и [[]]: a[0].length упадёт на первом.
• Обнуление «на лету» в задаче set zeroes.

Что спросят на собесе

• Поверни матрицу на месте.
• Обойди матрицу по спирали.
• Найди элемент в матрице с отсортированными строками и столбцами.
• Посчитай острова (связь с модулем графов).