54. Spiral Matrix

Задача

Дана матрица m×n. Верните все её элементы в спиральном порядке.

Примеры

Пример 1

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Пример 2

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Решение

Решение

/**
 * Вариант: Симуляция движения (Direction Vectors)
 *
 * Сложность по времени: O(m * n)
 * - Проходим каждый элемент один раз.
 *
 * Сложность по памяти: O(m * n)
 * - Используем матрицу visited такого же размера, чтобы не ходить по кругу.
 * - Можно оптимизировать до O(1), если разрешено менять исходную матрицу (например, заменять числа на null).
 */
var spiralOrder = function(matrix) {
    const rows = matrix.length;
    const cols = matrix[0].length;
    const directions = [
        [0, 1],
        [1, 0],
        [0, -1],
        [-1, 0]
    ];
 
    const visited = Array.from({
        length: rows
    }, () => Array(cols).fill(false));
    let directionIndex = 0;
    let r = 0;
    let c = 0;
 
    const result = [];
 
    while (result.length < rows * cols) {
        visited[r][c] = true;
 
        const value = matrix[r][c];
        result.push(value);
 
        const move = directions[directionIndex];
        const moveR = move[0];
        const moveC = move[1];
 
        const nextR = r + moveR;
        const nextC = c + moveC;
 
        if (nextR >= 0 && nextR < rows && nextC >= 0 && nextC < cols && !visited[nextR][nextC]) {
            r = nextR;
            c = nextC;
        } else {
            directionIndex = (directionIndex + 1) % 4;
 
            const move = directions[directionIndex];
            r += move[0];
            c += move[1];
        }
    }
 
    return result;
};

Решение 2 (Layer-by-Layer)

/**
 * Вариант: Симуляция через границы (Layer-by-Layer)
 *
 * Сложность по времени: O(m * n)
 * - Мы посещаем каждый элемент матрицы ровно один раз.
 *
 * Сложность по памяти: O(1)
 * - Мы храним только 4 переменные для границ и индекс результата.
 * - (Массив результата не считается за доп. память в контексте сложности алгоритма).
 */
var spiralOrder = function(matrix) {
    const result = [];
    if (!matrix.length) return result;
 
    let top = 0;
    let bottom = matrix.length - 1;
    let left = 0;
    let right = matrix[0].length - 1;
 
    while (top <= bottom && left <= right) {
        // 1. Идем ВПРАВО (по верхней границе)
        for (let i = left; i <= right; i++) {
            result.push(matrix[top][i]);
        }
        top++; // Верхняя граница опускается
 
        // 2. Идем ВНИЗ (по правой границе)
        for (let i = top; i <= bottom; i++) {
            result.push(matrix[i][right]);
        }
        right--; // Правая граница сдвигается влево
 
        // ВАЖНАЯ ПРОВЕРКА:
        // Если границы пересеклись после сдвигов выше, нужно прервать цикл,
        // иначе мы пройдемся обратно по уже пройденной строке/столбцу.
        if (top > bottom || left > right) break;
 
        // 3. Идем ВЛЕВО (по нижней границе)
        for (let i = right; i >= left; i--) {
            result.push(matrix[bottom][i]);
        }
        bottom--; // Нижняя граница поднимается
 
        // 4. Идем ВВЕРХ (по левой границе)
        for (let i = bottom; i >= top; i--) {
            result.push(matrix[i][left]);
        }
        left++; // Левая граница сдвигается вправо
    }
 
    return result;
};