Valid Sudoku

main.md

Question

Approach

I scan the 9×9 board once and validate three constraints simultaneously. I keep three collections: one for rows, one for columns, and one for the 3×3 sub-boxes. For each filled cell (r, c) with digit d, I check if d already exists in row[r], col[c], or box[r//3][c//3]. If it does, the board is invalid; otherwise I insert d into all three.

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(3)] for _ in range(3)]

        for r in range(9):
            for c in range(9):
                ch = board[r][c]
                if ch == '.':
                    continue
                if ch in rows[r] or ch in cols[c] or ch in boxes[r//3][c//3]:
                    return False
                rows[r].add(ch)
                cols[c].add(ch)
                boxes[r//3][c//3].add(ch)
        return True

Complexities

• Time: O(1)
• Space: O(1)