A-007● Day 072026.05.09mediumleetcode #36neetcode150

Valid Sudoku

#array#hash-table#matrix

Problem

· problem

P.007

Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition. Note: A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules.

constraints

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

// paraphrased summary — see source for full text

examples

example 1input → output

[["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

example 2input → output

[["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

Pre-solve

· pre-solve

● 1list shown→● 2select→● 3reveal

☐
Do we need to validate all three rules (rows, columns, and 3x3 boxes) simultaneously?
☐
What does 'only the filled cells need to be validated' mean?
☐
If a digit appears twice in the same row, is the board automatically invalid?
☐
Can we assume the input board is always exactly 9x9?
☐
Should we return which cell has the conflict?
☐
Do we need to check if the Sudoku board is solvable?

check the items you would ask, then press confirm

// session-only state — refresh resets (repeatable practice)

Logic Structure

· logic

● 1slots shown→● 2pick per slot→● 3reveal

// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.

step 1· Initialize tracking structures

○

cols = collections.defaultdict(set)

○

cols = {}

○

cols = set()

step 2· Iterate through all cells

○

for r in range(9):

○

for r in range(8):

○

for row in board:

step 3· Skip empty cells│ │ nested

○

if board[r][c] == ".":

○

if board[r][c] == 0:

○

if not board[r][c]:

step 4· Check for conflicts│ │ nested

○

board[r][c] in rows[r]

○

board[r][c] == rows[r]

○

rows[r].get(board[r][c])

step 5· Map cell to 3x3 box│ │ nested

○

or board[r][c] in squares[(r // 3, c // 3)]

○

squares[(r // 2, c // 2)]

○

squares[(r % 3, c % 3)]

step 6· Track seen values│ │ nested

○

cols[c].add(board[r][c])

○

cols[c].append(board[r][c])

○

cols[c] = {board[r][c]}

pick one option per slot

// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.

Solve · Trace

· solve

solution.py

class Solution:

    def isValidSudoku(self, board: List[List[str]]) -> bool:

        cols = collections.defaultdict(set)

        rows = collections.defaultdict(set)

        squares = collections.defaultdict(set)  # key = (r /3, c /3)

        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

mental dry-run cases

// walk each case in your head; expand the worked example below if stuck.

case 1

[["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

case 2

[["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

// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.