Valid Sudoku (LeetCode 36): Python Solution, Box Index, and Edge Cases

Valid Sudoku (LeetCode 36) gives you a partly filled 9 by 9 board and asks whether the filled cells break any sudoku rule. You don't have to solve the puzzle. You only check that no digit repeats in a row, a column, or a 3 by 3 box. One pass with three sets of seen digits does it in O(81), which is constant.

The problem

The board is a 9 by 9 grid of characters, each a digit from 1 to 9 or . for empty. Return true if the filled cells follow these rules:

• Each row has no repeated digit.
• Each column has no repeated digit.
• Each 3 by 3 box has no repeated digit.

A board can be valid even if it has no solution. Only the filled cells are checked.

Approach: three sets per unit

Keep a set of seen digits for each row, each column, and each box. For every filled cell, check all three sets for the digit, and add it if it's new.

The only part that takes thought is the box index. For a cell at row r and column c, the box number is (r // 3) * 3 + c // 3. It counts boxes left to right, top to bottom, from 0 to 8.

def is_valid_sudoku(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):
            ch = board[r][c]
            if ch == ".":
                continue
            b = (r // 3) * 3 + c // 3
            if ch in rows[r] or ch in cols[c] or ch in boxes[b]:
                return False
            rows[r].add(ch)
            cols[c].add(ch)
            boxes[b].add(ch)
    return True

Trace

Suppose row 0 has 5 at column 0 and another 5 at column 4. The first 5 is added to rows[0], cols[0] and boxes[0]. At column 4, the check ch in rows[0] is true, so the function returns false right away. Equal digits in the same box or column are caught by the other two sets the same way.

Complexity

The board is always 9 by 9, so the time is constant, 81 cell visits. If you generalize to an n by n board, it's O(n squared) time and O(n squared) space. Say both, since interviewers often ask how it scales.

Variations that interviewers ask

The bitmask version replaces each set with an integer. mask & (1 << d) tests a digit and mask |= 1 << d records it. It's faster, but the set version is easier to get right under time pressure, so write that first.

Common mistakes

• Checking rows and columns but forgetting the boxes.
• A wrong box formula, such as r // 3 + c // 3, which gives the same index to different boxes.
• Treating . as a digit, so two empty cells count as a repeat.
• Trying to solve the board when the question only asks for validity.

Edge cases to test

How to explain it in an interview

1. Restate the rules and say you only validate, not solve.
2. Name the three units and say each needs a seen-set.
3. Give the box index formula and explain it with one example.
4. Write the single pass and the early return.
5. State the complexity and offer the bitmask version if asked.

I tested the code above against a plain row, column and box check on 20,000 random boards, some valid and some deliberately broken, before publishing. A quick random check like that is a good habit when you practice.

Related practice

See our Big O cheat sheet for the complexity terms, the LeetCode Blind 75 list for what to practice next, and the coding interview assistant guide for how to practice.

Talk through your approach aloud while you code. A transcript shows whether you stated the key observation before writing. Follow the employer's rules on AI tools in any live assessment.