What pattern does the Valid Sudoku problem use?

The problem follows an array scanning plus hash lookup pattern where each row, column, and 3x3 sub-box is scanned and checked with hash sets.

Why do I need separate hash sets for rows, columns, and sub-boxes?

Each dimension must be validated independently; separate hash sets prevent conflicts and allow constant-time duplicate detection within rows, columns, and sub-boxes.

How do I map a cell to its 3x3 sub-box index?

Use integer division: subBoxIndex = (row / 3) * 3 + (col / 3). This uniquely identifies each of the nine 3x3 sub-boxes efficiently.

Can empty cells affect the validation?

No, empty cells represented by '.' are skipped during validation. Only filled cells are inserted into hash sets, avoiding false duplicates.

What is the main failure mode to watch for in this problem?

The primary failure mode is duplicates appearing in any row, column, or sub-box. Missing a sub-box check or miscomputing indices causes false positives or negatives.

#36

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）注意：一个有效的数独（部分已被填充）不一…

数组哈希表矩阵

题目描述

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

示例 1：

输入：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"]]
输出：true

示例 2：

输入：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"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'

lightbulb

解题思路

方法一：一次遍历

有效的数独满足以下三个条件：

每一行中的数字都不重复；
每一列中的数字都不重复；
每一个 $3 \times 3$ 的宫格中的数字都不重复。

遍历数独，对于每个数字，判断其所在的行、列以及 $3 \times 3$ 的宫格是否已经出现过该数字，如果是，则返回 false。遍历结束，返回 true。

时间复杂度 $O(C)$ ，空间复杂度 $O(C)$ ，其中 $C$ 是数独中的空格数。本题中 $C=81$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [[False] * 9 for _ in range(9)]
        col = [[False] * 9 for _ in range(9)]
        sub = [[False] * 9 for _ in range(9)]
        for i in range(9):
            for j in range(9):
                c = board[i][j]
                if c == '.':
                    continue
                num = int(c) - 1
                k = i // 3 * 3 + j // 3
                if row[i][num] or col[j][num] or sub[k][num]:
                    return False
                row[i][num] = True
                col[j][num] = True
                sub[k][num] = True
        return True

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you recognize how duplicate checks in rows, columns, and sub-boxes can be optimized using hash sets?
question_mark
Can you map each board cell to its 3x3 sub-box index without extra loops?
question_mark
Will you handle empty cells efficiently to avoid unnecessary hash operations?

warning

常见陷阱

外企场景

error
Confusing the 3x3 sub-box indexing, which can lead to missed duplicates or false positives.
error
Checking only rows and columns but forgetting sub-boxes, which breaks Sudoku rules.
error
Attempting to scan sub-boxes with nested loops for every cell instead of using precomputed hash sets, causing redundant computations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Determine the minimum changes required to make a partially filled Sudoku board valid.
arrow_right_alt
Validate a Sudoku board of arbitrary size N x N with sqrt(N) x sqrt(N) sub-boxes.
arrow_right_alt
Implement a Sudoku solver that fills empty cells while maintaining validity at each step.

help

常见问题

外企场景

继续练习

#37 解数独 #73 矩阵置零 #840 矩阵中的幻方