0036-valid-sudoku.js

/**
 * Hash Map - Matrix
 * Time O(ROWS * COLS) | Space O(ROWS * COLS)
 * https://leetcode.com/problems/valid-sudoku/
 * @param {character[][]} board
 * @return {boolean}
 */

 var isValidSudoku = function (board) {
    let row = [];
    let col = [];
    let squares = new Map();
    // Creating new col, row and sqaures Sets
    for (let i = 0; i < 9; i++) {
        let newRowSet = new Set();
        let newColSet = new Set();
        row.push(newRowSet);
        col.push(newColSet);
        for (let j = 0; j < 9; j++) {
            squares.set(`${Math.floor(i / 3)}:${Math.floor(j / 3)}`, new Set());
        }
    }
    
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] === '.') {
                continue;
            }
            if (
                row[i].has(board[i][j]) ||
                col[j].has(board[i][j]) ||
                squares
                    .get(`${Math.floor(i / 3)}:${Math.floor(j / 3)}`)
                    .has(board[i][j])
            ) {
                return false;
            }
            row[i].add(board[i][j]);
            col[j].add(board[i][j]);
            squares
                .get(`${Math.floor(i / 3)}:${Math.floor(j / 3)}`)
                .add(board[i][j]);
        }
    }
    return true;
};

/**
 * Hash Map - Matrix
 * Time O(ROWS * COLS) | Space O(ROWS * COLS)
 * https://leetcode.com/problems/valid-sudoku/
 * @param {character[][]} board
 * @return {boolean}
 */
 var isValidSudoku = (board) => {
    const boards = 3;
    const [ boxes, cols, rows ] = getBoards(boards);/* Time O(ROWS * COLS) | Space O(ROWS * COLS) */

    return searchGrid(board, boxes, cols, rows);    /* Time O(ROWS * COLS) | Space O(ROWS * COLS) */
};

var initBoard = (rows, cols) => new Array(rows).fill()
    .map(() => new Array(cols).fill(false));

var getBoards = (boards) => {
    const [ rows, cols ] = [ 9, 9 ];

    return new Array(boards).fill()
        .map(() => initBoard(rows, cols))
}

var searchGrid = (board, boxes, cols, rows) => {
    const [ _rows, _cols ] = [ 9, 9 ];

    for (let row = 0; row < _rows; row++) {/* Time O(ROWS)*/
        for (let col = 0; col < _cols; col++) {/* Time O(COLS)*/
            const char = board[row][col];
            const index = (Math.floor(row / 3) * 3) + Math.floor(col / 3);

            const isEmpty = char === '.';
            if (isEmpty) continue;

            const hasMoved = boxes[index][(char - 1)] || cols[col][(char - 1)] || rows[row][(char - 1)];
            if (hasMoved) return false;

            rows[row][(char - 1)] = true;               /* Space O(ROWS * COLS)*/
            cols[col][(char - 1)] = true;               /* Space O(ROWS * COLS)*/
            boxes[index][(char - 1)] = true;            /* Space O(ROWS * COLS)*/
        }
    }

    return true;
}

/**
 * Array - Fixed Size
 * Time O(ROWS * COLS) | Space O(CELLS)
 * https://leetcode.com/problems/valid-sudoku/
 * @param {character[][]} board
 * @return {boolean}
 */
 var isValidSudoku = (board) => {
    const [ boards, cells ] = [ 3, 9];
    const [ boxes, rows, cols ] = getBoards(boards, cells);/* Time O(ROWS * COLS) | Space O(CELLS) */

    return searchGrid(board, boxes, rows, cols);           /* Time O(ROWS * COLS) | Space O(CELLS) */
}

var getBoards = (boards, cells) => new Array(boards).fill()
    .map(() => new Array(cells).fill(0));

var searchGrid = (board, boxes, rows, cols) => {
    const [ _rows, _cols ] = [ 9, 9 ];

    for (let row = 0; row < _rows; row++) {/* Time O(ROWS)*/
        for (let col = 0; col < _cols; col++) {/* Time O(COLS)*/
            const char = board[row][col];
            const position = 1 << (char - 1);
            const index = (Math.floor(row / 3) * 3) + Math.floor(col / 3);

            const isEmpty = char === '.';
            if (isEmpty) continue;

            const hasMoved = (boxes[index] & position) || (cols[col] & position) || (rows[row] & position);
            if (hasMoved) return false;

            rows[row] |= position;                 /* Space O(CELLS)*/
            cols[col] |= position;                 /* Space O(CELLS)*/
            boxes[index] |= position;              /* Space O(CELLS)*/
        }
    }

    return true;
}