Check whether a partially filled 9 by 9 Sudoku board is valid. No digit may repeat in any row, in any column, or in any of the nine 3 by 3 boxes. Empty cells are ignored, and the board does not need to be solvable.
DSA Animator › DSA Revision › Matrix › Valid Sudoku
Remember: one pass, 27 sets, three checks per cell. Box index equals row over 3, times 3, plus column over 3. The video solves Valid Sudoku (LeetCode 36, Medium) with the Hash Sets pattern from the Matrix topic, and you can replay every step in the interactive Valid Sudoku animation.
Check whether a partially filled 9 by 9 Sudoku board is valid. No digit may repeat in any row, in any column, or in any of the nine 3 by 3 boxes. Empty cells are ignored, and the board does not need to be solvable.
This board looks fine at first glance. But it has two 8s in the top left box, so the answer is false.
You could check every row, then every column, then every box, in three separate passes. One pass with sets for all three is cleaner.
Keep 9 sets for the rows, 9 for the columns, and 9 for the boxes. The box index of a cell is row divided by 3, times 3, plus column divided by 3. For each filled cell, if its digit is already in its row, column or box set, the board is invalid. Otherwise add the digit to all three sets.
Row 0 adds 8, 3 and 7 to their sets. Row 1 adds 6, 1, 9 and 5. In row 2, the 9 at column 1 is fine. Then the 8 at row 2, column 2 lands in box 0. Box 0 already holds the 8 from row 0, column 0. That is a repeat, so the board is invalid, and we return false. Column 0 also has a second 8 further down, but we can stop at the first repeat.
In code, create the 27 sets. Loop over all 81 cells and skip the empty ones. Compute the box index, and return false if the digit is in any of the three sets. Otherwise add it to all three. The board is always 9 by 9, so this is O of 1 time and space.
Remember: one pass, 27 sets, three checks per cell. Box index equals row over 3, times 3, plus column over 3.