{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Valid Sudoku – Solution & Complexity

Interview solutions
/
Valid Sudoku

Solution Walkthrough

  1. Step 1: Check each rule directly

    A straightforward approach is to validate every row, every column, and every 3 x 3 box separately. For each group, collect the non-zero digits you see and fail if a digit appears twice. This works well, but it conceptually scans the board multiple times even though the board is only 9 x 9.

  2. Step 2: Single-pass tracking with row, column, and box state

    Iterate through the board once. Ignore 0 because it means the cell is empty. For each filled cell, compute its box index with (row // 3) * 3 + (col // 3), then check whether that digit has already appeared in the current row, column, or box. If so, return false immediately; otherwise mark it as seen and continue. After all 81 cells are processed without a conflict, return true.

    def is_valid_sudoku(board: list[list[int]]) -> bool:
    rows = [[False] * 10 for _ in range(9)]
    cols = [[False] * 10 for _ in range(9)]
    boxes = [[False] * 10 for _ in range(9)]

    for row in range(9):
        for col in range(9):
            value = board[row][col]
            if value == 0:
                continue

            box = (row // 3) * 3 + (col // 3)
            if rows[row][value] or cols[col][value] or boxes[box][value]:
                return False

            rows[row][value] = True
            cols[col][value] = True
            boxes[box][value] = True

    return True

FAQ

See also

Practice Valid Sudoku online (run code in the browser)Find All Duplicates in an Array solution (medium)Rotate Image solution (medium)Search a 2D Matrix solution (medium)Set Matrix Zeroes solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?