Arrays

All about Arrays alogirthm

Some description

LinkIcon36. Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  • Each row must contain the digits 1-9 without repetition.
  • Each column must contain the digits 1-9 without repetition.
  • Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.

Example 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

Example 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
> Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

LinkIconsolution

Create three hashsets for: rows, cols, subgrids of 3x3, where key = index and value = Set.

Iterate over the board's each grid and check:

  • check set exists in hashset
  • if current grid is empty then continue
  • if current grid is in the sets (rows, colrs, 3x3 subgrids) then is invalid
  • otherwise it is valid then populate hashset

We will have something like this

row_hashset = {
  0: set(1,2,...,9) // row 0
  1: set(1,2,...,9) // row 1
}
 
col_hashset = {
  0: set(1,2,...,9) // col 0
  ...
}

For the subgrid3x3, we will divide the board in 3x3. this way:

  0,0  |  0,1  |  0,2
ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”
  1,0  |  1,1  |  1,2
ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”ā€”
  2,0  |  2,1  |  2,2

To do so, we will divide the row index by 3 and the column index by 3.

For example:

board[3][0], board[3][1], board[3][2]
> dividing by 3
board[3/3][0/3], board[3/3][1/3], board[3/3][2/3] => board[1][0], board[1][0], board[1][0]
> All these 3 belongs to 1,0 subgrid
 
So
subgrid3x3 = {
  "1,0": set(1,2,3...)
}

LinkIconCode

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
    const row_hashset = {}
    const col_hashset = {}
    const subgrid3x3 = {}
 
    for (let [row_idx, row_array] of board.entries()) {
        for (let [col_idx, item] of row_array.entries()) {
            // check set exists in map
            if (!(row_idx in row_hashset)) row_hashset[row_idx] = new Set()
            if (!(col_idx in col_hashset)) col_hashset[col_idx] = new Set()
            if (!(`${Math.floor(row_idx/3)},${Math.floor(col_idx/3)}`] in subgrid3x3)) subgrid3x3[`${Math.floor(row_idx/3)},${Math.floor(col_idx/3)}`] = new Set()
 
            // if current item is empty string -> continue
            if (item === ".") continue
 
            // if current item is in the set, return false
            if (row_hashset[row_idx].has(item)) return false
            if (col_hashset[col_idx].has(item)) return false
            if (subgrid3x3[`${Math.floor(row_idx/3)},${Math.floor(col_idx/3)}`].has(item)) return false
 
            // populating the sets
            row_hashset[row_idx].add(item)
            col_hashset[col_idx].add(item)
            subgrid3x3[[Math.floor(row_idx/3),Math.floor(col_idx/3)]].add(item)
        }
    }
 
    return true
};