MediumNeetCode150ArrayHash TableMatrix

Valid Sudoku

Determine if a 9x9 Sudoku board is valid. Only filled cells need validation.

Examples

Input
board = [["5","3",".",".","7",".",".",".","."],...]
Output
true

The board is valid.

Constraints

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

Approaches

Check rows,cols,boxes separately.

CodeT: O(n^2) | S: O(n)
def isValidSudoku(board):
    for row in board:
        nums=[x for x in row if x!='.']
        if len(nums)!=len(set(nums)): return False
    for c in range(9):
        col=[board[r][c] for r in range(9) if board[r][c]!='.']
        if len(col)!=len(set(col)): return False
    for br in range(3):
        for bc in range(3):
            box=[board[br*3+i][bc*3+j] for i in range(3) for j in range(3) if board[br*3+i][bc*3+j]!='.']
            if len(box)!=len(set(box)): return False
    return True

9 sets each for rows,cols,boxes.

CodeT: O(n^2) | S: O(n)
def isValidSudoku(board):
    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
            bi=(r//3)*3+(c//3)
            if v in rows[r] or v in cols[c] or v in boxes[bi]: return False
            rows[r].add(v); cols[c].add(v); boxes[bi].add(v)
    return True

Same approach.

Diagram

box_idx = (r//3)*3 + (c//3)
CodeT: O(1) | S: O(1)
def isValidSudoku(board):
    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
            bi=(r//3)*3+(c//3)
            if v in rows[r] or v in cols[c] or v in boxes[bi]: return False
            rows[r].add(v); cols[c].add(v); boxes[bi].add(v)
    return True

Complexity Comparison

Three Separate Checks
T: O(n^2)S: O(n)

Check rows,cols,boxes separately.

Hash Sets
T: O(n^2)S: O(n)

9 sets each for rows,cols,boxes.

Single Pass with Hash Sets
T: O(1)S: O(1)

Same approach.

Common Mistakes

Wrong 3x3 box index

Checking entire board not just filled cells

Not handling '.' properly

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems