36. Valid Sudoku

Задача

Дана доска судоку 9×9. Проверьте, корректна ли она: в строках, столбцах и блоках 3×3 нет повторяющихся цифр 1-9.

Примеры

Пример 1

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Пример 2

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false

Пояснение

То же, что Пример 1, но 5 в левом верхнем углу заменена на 8. В левом верхнем блоке 3×3 теперь две восьмёрки — доска невалидна.

Решение

Решение

/**
 * Time Complexity: O(1) или O(81) - один проход по доске 9x9 (константа)
 * Space Complexity: O(1) или O(243) - максимум 9 цифр в 27 множествах (константа)
 * 
 * Решение: за один проход проверяем все три правила одновременно,
 * используя Set для строк, столбцов и квадратов 3x3
 */
var isValidSudoku = function(board) {
    // Массивы Set для каждой строки, столбца и квадрата 3x3
    const rows = Array.from({
        length: 9
    }, () => new Set());
    const cols = Array.from({
        length: 9
    }, () => new Set());
    const boxes = Array.from({
        length: 9
    }, () => new Set());
 
    for (let r = 0; r < 9; r++) {
        for (let c = 0; c < 9; c++) {
            const cell = board[r][c];
 
            // Пропускаем пустые клетки
            if (cell === '.') continue;
 
            // Вычисляем индекс квадрата 3x3
            // Формула: (row / 3) * 3 + (col / 3)
            const boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3);
 
            // Проверяем, была ли цифра уже встречена
            if (rows[r].has(cell) ||
                cols[c].has(cell) ||
                boxes[boxIndex].has(cell)) {
                return false;
            }
 
            // Добавляем цифру во все три множества
            rows[r].add(cell);
            cols[c].add(cell);
            boxes[boxIndex].add(cell);
        }
    }
 
    return true;
};