LeetCode 036 - Valid Sudoku

2026-04-09

medium　array

You are given a 9 x 9 Sudoku board board. A Sudoku board is valid if the following rules are followed:

• Each row must contain the digits 1-9 without duplicates.
• Each column must contain the digits 1-9 without duplicates.
• Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without duplicates.

Return true if the Sudoku board is valid, otherwise return false

Note: A board does not need to be full or be solvable to be valid.

Example 1:

Input: board =
[["1","2",".",".","3",".",".",".","."],
 ["4",".",".","5",".",".",".",".","."],
 [".","9","8",".",".",".",".",".","3"],
 ["5",".",".",".","6",".",".",".","4"],
 [".",".",".","8",".","3",".",".","5"],
 ["7",".",".",".","2",".",".",".","6"],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".","4","1","9",".",".","8"],
 [".",".",".",".","8",".",".","7","9"]]

Output: true

Example 2:

Input: board =
[["1","2",".",".","3",".",".",".","."],
 ["4",".",".","5",".",".",".",".","."],
 [".","9","1",".",".",".",".",".","3"],
 ["5",".",".",".","6",".",".",".","4"],
 [".",".",".","8",".","3",".",".","5"],
 ["7",".",".",".","2",".",".",".","6"],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".","4","1","9",".",".","8"],
 [".",".",".",".","8",".",".","7","9"]]

Output: false

Explanation: There are two 1's in the top-left 3x3 sub-box.

Constraints:

board.length == 9board[i].length == 9board[i][j] is a digit 1-9 or '.'.

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.

Solution 1:

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        # Brute-force Solution
        # We validate the Sudoku board by checking three main rules independently.
        # Note: Since the board is strictly 9x9, the strict Time and Space complexity is O(1).
        # If generalized for an N x N board, it would be Time: O(N^2) and Space: O(N).

        # 1. Check if each row is valid (no duplicate digits from 1-9)
        for i in board:
            digit_set = set()
            for j in i:
                if j == ".":
                    continue
                # If the digit is already in our set, the row is invalid
                if j in digit_set:
                    return False
                digit_set.add(j)
                
        # 2. Check if each column is valid
        for i in range(9):
            digit_set = set()
            for j in range(9):
                # i represents the column index, j represents the row index
                if board[j][i] == ".":
                    continue
                if board[j][i] in digit_set:
                    return False
                digit_set.add(board[j][i])
                
        # 3. Check if each 3x3 sub-box is valid
        x = 0
        for _ in range(3):
            y = 0
            for _ in range(3):
                digit_set = set() # Use set instead of list for O(1) lookup time
                # Iterate through the specific 3x3 sub-box boundaries
                for i in range(x, x + 3):
                    for j in range(y, y + 3):
                        if board[i][j] == ".":
                            continue
                        if board[i][j] in digit_set:
                            return False
                        digit_set.add(board[i][j])
                # Move to the next 3x3 box in the same row block
                y += 3
            # Move down to the next row block of 3x3 boxes
            x += 3
            
        # If all checks pass, the board is valid
        return True

Solution 2:

from collections import defaultdict

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        # Optimal One-Pass Solution
        # We use hash sets to keep track of the digits we've seen in each row, column, and 3x3 box.
        # This allows us to validate the board by iterating through it only exactly once.
        
        # Time Complexity: O(1) strictly since the board is always 9x9. 
        # (Or O(N^2) if generalized to an N x N board).
        # Space Complexity: O(1) strictly, as the maximum number of elements in all sets combined is 81.
        
        # Initialize dictionaries where each key maps to a Set.
        # This prevents KeyError when we try to add or check items for the first time.
        rows = defaultdict(set)
        cols = defaultdict(set)
        boxes = defaultdict(set) # Key will be a tuple: (row // 3, col // 3)
        
        for r in range(9):
            for c in range(9):
                current_val = board[r][c]
                
                # Skip empty cells
                if current_val == ".":
                    continue
                    
                # Check if the current value already exists in the corresponding row, col, or box
                if (current_val in rows[r] or 
                    current_val in cols[c] or 
                    current_val in boxes[(r // 3, c // 3)]):
                    return False # Found a duplicate, invalid Sudoku!
                
                # If not found, add the value to our tracker sets
                rows[r].add(current_val)
                cols[c].add(current_val)
                boxes[(r // 3, c // 3)].add(current_val)
                
        # If we successfully iterate through the entire board without conflicts, it's valid!
        return True

結語：

這題在處理前兩個條件（驗證行與列）時相對直觀，但在解第三個條件驗證 3x3 九宮格時確實讓我卡了一陣子。

在最初的暴力解 (Brute-force) 中，可以透過增加 x 與 y 兩個座標指標，搭配迴圈遞增來控制九宮格的掃描邊界，成功實現了完整的盤面檢查。

至於更優雅的進階解法，則是以空間換取時間。透過引入 collections.defaultdict(set) 來準備分類容器，並搭配**「座標整數除法 (r // 3, c // 3)」**的數學技巧，將二維座標映射到對應的 3x3 區塊編號中。這個解法不僅省去了繁瑣的邊界控制迴圈，更讓我們能在只逛盤面一次的情況下，同時完成三個條件的驗證，讓程式碼的簡潔度與執行效能都達到最佳化！