LeetCode - 36. Valid Sudoku

Thoughts:

I choose hash map to solve this problem. It’s about to check does the sudoku is valid by the rules or not !!! Don’t need to figure out the solution, just need to check if the sudoku is valid. The time complexity is O(1) because the board is always 9x9.

Thoughts visuzlization:

only check the filled cells!!!
the empty cells are represented by '.'
the 9x9 board is like this

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"]
]

first, check the filled cells in a row is unique or not
second, check the filled cells in a column is unique or not
third, check the filled cells in a 3x3 box is unique or not
so use a hash map for storing the index as key, the number's set as value
assuming the index of row is i, the index of column is j
row and column are the same as the index of the board
the difficult part is to figure out the index of the 3x3 box

  0 1 2 3 4 5 6 7 8
0 a a a b b b c c c
1 a a a b b b c c c
2 a a a b b b c c c
3 d d d e e e f f f
4 d d d e e e f f f
5 d d d e e e f f f
6 g g g h h h i i i
7 g g g h h h i i i
8 g g g h h h i i i

use a, b, c, d, e, f, g, h, i to represent the 3x3 box (alphabet is more readable)
    0  1  2  3  4  5  6  7  8
and I can find the pattern of the index of the 3x3 box
the index of the 3x3 box is (i//3)*3 + j//3

if we can check all the exsiting elements in the board are following the rules
then the sudoku is valid

Code:

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
  const rows = new Map();
  const cols = new Map();
  const subBoxes = new Map();
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      const cell = board[i][j];
      if (cell === '.') continue;
      if (
        rows.get(i)?.has(cell) ||
        cols.get(j)?.has(cell) ||
        subBoxes.get(getSubBoxKey(i, j))?.has(cell)
      ) {
        return false;
      }
      rows.set(i, (rows.get(i) || new Set()).add(cell));
      cols.set(j, (cols.get(j) || new Set()).add(cell));
      subBoxes.set(
        getSubBoxKey(i, j),
        (subBoxes.get(getSubBoxKey(i, j)) || new Set()).add(cell),
      );
    }
  }
  return true;
};

const getSubBoxKey = (i, j) => Math.floor(i / 3) * 3 + Math.floor(j / 3);

Reference

Original link