304. Valid Sudoku
Medium
Constraint Sets
Hashing
Problem
Given a partially filled 9 by 9 Sudoku board, determine whether the current board is valid. Each row, each column and each 3 by 3 sub-box must contain each digit from 1 through 9 at most once. Empty cells are represented by a period.
Examples
Example 1
Input: [["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: [["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
Constraints
� board has exactly 9 rows.
� Every row has exactly 9 cells.
� Each cell is a digit from 1 through 9 or a period.
Hints
?? Track values already observed in every row.
?? Do the same for every column.
?? A cell at row r and column c belongs to box (floor(r / 3), floor(c / 3)).
Expected Complexity
Time: O(81)
Space: O(81)
Follow-up
Can you encode each row, column and box using bit masks instead of hash sets?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[["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"]]Expected
true