DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Valid Sudoku - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

For a 9×9 Sudoku board, this approach uses three hash maps to track numbers seen in each row, column, and 3×3 sub-box respectively while iterating through the board.

  • Row map: maps row index to set of numbers seen in that row

  • Column map: maps column index to set of numbers seen in that column

  • Sub-sudoku map: maps each 3×3 sub-grid to the set of numbers seen in that sub-grid.

    Note: Each sub-grid is identified by its row group and column group, calculated as the row index divided by 3 and the column index divided by 3.

For each non-empty cell, if the number already exists in any corresponding set, the board is invalid; otherwise, the number is added to the appropriate sets.
If all checks pass for every cell, the board is valid.

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # Track seen values in rows, columns, and 3x3 sub-sudoku boxes
        row_map = collections.defaultdict(set)  # row index -> values set
        col_map = collections.defaultdict(set)  # col index -> values set
        sub_sudoku_map = collections.defaultdict(set) # (row // 3, col // 3) -> values set

        for row in range(9):
            for col in range(9):
                value = board[row][col]
                if value == '.':
                    continue
                if (value in row_map[row] or 
                      value in col_map[col] or
                      value in sub_sudoku_map[(row // 3, col // 3)]):
                      return False
                row_map[row].add(value)
                col_map[col].add(value)
                sub_sudoku_map[(row // 3, col // 3)].add(value)
        return True

Complexity Analysis

Here, the size of the Sudoku board is 9×9.

  • Time Complexity: O(1)
    The board has a fixed size of 9×9 (81 cells). Each cell is visited exactly once, and all set operations (check and add) take constant time. Therefore, the time complexity is O(81) = O(1).

  • Space Complexity: O(1) In the worst case, the three maps (rows, columns, sub-sudokus) store at most 81 numbers each.
    Since the board size is fixed, the total space used does not scale with input.

Note:
For a general N×N board, both time and space complexities would scale as O(N²).
However, when N is a fixed number (like 9 for a standard Sudoku), both complexities are effectively constant, O(1).