36. Valid Sudoku

LeetCode 36. Valid Sudoku

Description

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

1. Each row must contain the digits 1-9 without repetition.

2. Each column must contain the digits 1-9 without repetition.

3. 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.

Constraints:

• board.length == 9

• board[i].length == 9

• board[i][j] is a digit or '.'.

Tags

Hash Table

Solution

Box index = row / 3 * 3 + col / 3

We initialize 3*9=27 hash tables (mapping from cell value to count) for 9 row, 9 columns and 9 boxes, and iterate only once over the board. For each cell value (skip if it is an empty cell), if it has already been stored in one of 27 hash tables, we return false. Otherwise, we add 1 to the respective slot. After the loop, return true.

Complexity

• Time complexity: $O(1)$

• Space complexity: $O(1)$

Code

func isValidSudoku(board [][]byte) bool {
	rows, cols, boxes := [9][9]int{}, [9][9]int{}, [9][9]int{}
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if board[i][j] == '.' {
				continue
			}
			boxIdx, v := i/3*3+j/3, board[i][j]-'1'
			rows[i][v]++
			cols[j][v]++
			boxes[boxIdx][v]++
			if rows[i][v] > 1 || cols[j][v] > 1 || boxes[boxIdx][v] > 1 {
				return false
			}
		}
	}
	return true
}

Reference

1. 有效的数独