Valid Sudoku

Difficulty: Medium Source: NeetCode

Problem

Determine if a 9 × 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1–9 with no repetition.
2. Each column must contain the digits 1–9 with no repetition.
3. Each of the nine 3 × 3 sub-boxes must contain the digits 1–9 with no repetition.

Note: A Sudoku board does not need to be solvable to be valid. Only already-filled cells are validated. Empty cells are represented by '.'.

Example 1: Input: a standard partially-filled Sudoku board Output: true

Example 2: Input: a board with 8 appearing twice in the top row Output: false

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Hash Sets — detecting duplicates efficiently
• 2D array indexing — mapping (row, col) to box index
• String vs integer handling — board cells are strings '1'–'9' and '.'

1. Three Separate Passes

Intuition

Validate each constraint independently: check all rows for duplicates, then check all columns, then check all 3×3 boxes. Each check uses a set to detect repeated digits. Although this is three passes, it is still O(81) = O(1) since the board is a fixed 9×9 grid.

Algorithm

1. For each of 9 rows: collect non-'.' cells into a list; return false if any duplicates.
2. For each of 9 columns: same check.
3. For each of 9 boxes (indexed by box_row 0–2, box_col 0–2): collect the 9 cells in each 3×3 block; return false if any duplicates.
4. Return true.

Solution

def isValidSudoku(board):
    # Check rows
    for row in board:
        seen = set()
        for c in row:
            if c == '.':
                continue
            if c in seen:
                return False
            seen.add(c)

    # Check columns
    for col in range(9):
        seen = set()
        for row in range(9):
            c = board[row][col]
            if c == '.':
                continue
            if c in seen:
                return False
            seen.add(c)

    # Check 3x3 boxes
    for box_row in range(3):
        for box_col in range(3):
            seen = set()
            for r in range(3):
                for c in range(3):
                    val = board[box_row * 3 + r][box_col * 3 + c]
                    if val == '.':
                        continue
                    if val in seen:
                        return False
                    seen.add(val)

    return True


board = [
    ["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"],
]
print(isValidSudoku(board))  # True

invalid_board = [row[:] for row in board]
invalid_board[0][1] = "5"   # duplicate '5' in first row
print(isValidSudoku(invalid_board))  # False

Complexity

• Time: O(81) = O(1) — fixed board size
• Space: O(9) = O(1) — at most 9 elements in any set at once

2. Single Pass with Keyed Sets

Intuition

Instead of three separate loops, visit each cell once and simultaneously check all three constraints using one set per constraint type. The key insight is encoding the constraint identity into the set entry itself:

• Row check: store (row, digit) in a rows set
• Column check: store (col, digit) in a cols set
• Box check: store (row // 3, col // 3, digit) in a boxes set

If any of these tuples is already in its respective set, return false immediately.

Algorithm

1. Create three empty sets: rows, cols, boxes.
2. For each cell (r, c) with value val:
   • Skip if val == '.'.
   • If (r, val) in rows or (c, val) in cols or (r//3, c//3, val) in boxes: return false.
   • Add the tuples to each set.
3. Return true.

flowchart LR
    A(["visit cell (0,0) val='5'"])
    A --> B["check rows: (0,'5') — not seen"]
    B --> C["check cols: (0,'5') — not seen"]
    C --> D["check boxes: (0,0,'5') — not seen"]
    D --> E["add all three tuples, continue"]

Solution

def isValidSudoku(board):
    rows = set()
    cols = set()
    boxes = set()

    for r in range(9):
        for c in range(9):
            val = board[r][c]
            if val == '.':
                continue

            if (r, val) in rows:
                return False
            rows.add((r, val))

            if (c, val) in cols:
                return False
            cols.add((c, val))

            box_key = (r // 3, c // 3, val)
            if box_key in boxes:
                return False
            boxes.add(box_key)

    return True


board = [
    ["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"],
]
print(isValidSudoku(board))  # True

board[0][1] = "5"  # duplicate in row 0
print(isValidSudoku(board))  # False

Complexity

• Time: O(1) — 81 cells, fixed
• Space: O(1) — at most 81 * 3 = 243 entries across all sets, which is constant

Common Pitfalls

Forgetting to skip '.' cells. Empty cells should not be validated — they represent unfilled positions. Always check if val == '.' before processing.

Box index calculation. The box for cell (r, c) is identified by (r // 3, c // 3). Box (0,0) covers rows 0–2 and columns 0–2; box (1,2) covers rows 3–5 and columns 6–8.

Thinking the board must be solvable. Validity only requires that the existing digits do not violate the three rules. A board with all cells empty is valid. A board with the digit 5 in every cell of the first row is invalid — regardless of whether the rest of the board could be filled in.