💬 Discord
Sign In
NeetCode #104LC-36MediumArrays & HashingNC 150NC 250
← Back to All Problems

#104 · #36 · Valid Sudoku(有效的数独)

📌 Problem Statement & Constraints

Determine whether a partially filled 9x9 Sudoku board is valid. Only the filled cells need to be validated, against three rules: each row, each column, and each of the nine 3x3 sub-boxes must contain the digits 1-9 without repetition. Empty cells are represented by '.'. Constraints: board.length == board[i].length == 9, and each cell is a digit or '.'.

💡 Core Algorithmic Approaches

  1. The board size is fixed, so any solution is O(1); the interesting part is doing it cleanly in a single pass.
  2. Keep three families of hash sets: nine row sets, nine column sets, and nine box sets.
  3. Map each cell (r, c) to its box index with (r // 3) * 3 + (c // 3). This is the classic trick worth memorising.
  4. For each filled cell, test membership in all three sets; if any already contains the digit, the board is invalid. Otherwise insert into all three.

💻 Benchmark Python3 Implementation

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        for r in range(9):
            for c in range(9):
                v = board[r][c]
                if v == ".":
                    continue
                b = (r // 3) * 3 + (c // 3)      # box index 0..8
                if v in rows[r] or v in cols[c] or v in boxes[b]:
                    return False
                rows[r].add(v)
                cols[c].add(v)
                boxes[b].add(v)
        return True


# Bitmask variant: one integer per row/column/box instead of a set
class Solution2:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [0] * 9
        cols = [0] * 9
        boxes = [0] * 9
        for r in range(9):
            for c in range(9):
                v = board[r][c]
                if v == ".":
                    continue
                bit = 1 << (ord(v) - ord("1"))
                b = (r // 3) * 3 + (c // 3)
                if rows[r] & bit or cols[c] & bit or boxes[b] & bit:
                    return False
                rows[r] |= bit
                cols[c] |= bit
                boxes[b] |= bit
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) -- the board is a fixed 81 cells, so both variants run in constant time (O(81) with a tiny constant).
💾 Space Complexity
O(1) -- 27 sets (or 27 integers in the bitmask variant), independent of input size.

⚠️ Interview Pitfalls & Follow-ups

  • Wrong box index formula: it is (r // 3) * 3 + (c // 3), not (r // 3) + (c // 3) * 3 or a division by 9.
  • Forgetting to skip '.': the empty marker would be inserted into the sets and could trigger a false duplicate.
  • Validating only rows and columns: the 3x3 sub-box rule is the part candidates most often forget.
  • Trying to solve the Sudoku: the problem only asks whether the current partial board is valid, not whether it is solvable.