Solutions

# Hash set. Each small square can be indexed as (r // 3), (c // 3)
# hash-set

# Brute force, O(n^2) time, O(n) space
def isValidSudoku(board: list[list[str]]) -> bool:
    for row in range(9):
        seen = set()
        for i in range(9):
            if board[row][i] == ".":
                continue
            if board[row][i] in seen:
                return False
            seen.add(board[row][i])

    for col in range(9):
        seen = set()
        for i in range(9):
            if board[i][col] == ".":
                continue
            if board[i][col] in seen:
                return False
            seen.add(board[i][col])

    for square in range(9):
        seen = set()
        for i in range(3):
            for j in range(3):
                row = (square // 3) * 3 + i
                col = (square % 3) * 3 + j
                if board[row][col] == ".":
                    continue
                if board[row][col] in seen:
                    return False
                seen.add(board[row][col])
    return True

# Hash set, O(n^2) time, O(n) space
def isValidSudoku(board: list[list[str]]) -> bool:
    from collections import defaultdict
    cols = defaultdict(set)
    rows = defaultdict(set)
    squares = defaultdict(set)

    for r in range(9):
        for c in range(9):
            if board[r][c] == ".":
                continue
            if ( board[r][c] in rows[r]
                or board[r][c] in cols[c]
                or board[r][c] in squares[(r // 3, c // 3)]):
                return False

            cols[c].add(board[r][c])
            rows[r].add(board[r][c])
            squares[(r // 3, c // 3)].add(board[r][c])

    return True

# Bitmask, O(n^2) time, O(1) space
def is_valid_sudoku(board: list[list[str]]) -> bool:
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9
    for r in range(9):
        for c in range(9):
            num = board[r][c]
            if num != '.':
                bit = 1 << (int(num) - 1)
                if (rows[r] & bit) or \
                    (cols[c] & bit) or \
                    (boxes[(r // 3, c // 3)] & bit):
                    return False
                rows[r] |= bit
                cols[c] |= bit
                boxes[(r // 3, c // 3)] |= bit
    return True