Valid Sudoku LeetCode Problem 36 [Python Solution]

The Valid Sudoku LeetCode problem asks us to determine if a given 9x9 Sudoku board is valid according to the rules of Sudoku.

The rules are as follows:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3×3 sub-grids must contain the digits 1-9 without repetition.

Question

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

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

Let’s break down the problem step by step.

Problem Overview

We are given a 9×9 Sudoku board with some cells filled in, and our task is to check whether the board is valid based on the Sudoku rules.

Only the filled cells need to be validated; empty cells are considered valid.

This means that we don’t need to solve the Sudoku puzzle; we just need to verify if it follows the rules.

Example 1:

Let’s look at an example:

Input: 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"]]

Output: true

Explanation: This Sudoku board is valid because it adheres to all the Sudoku rules. Each row, column, and 3x3 sub-grid contains digits 1-9 without repetition.

Example 2:

Input: board =
[["8","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"]]

Output: false

Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

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

Understanding the Constraints

Before we dive into the solution, let’s understand the constraints of this problem.

The board has a fixed size of 9x9, meaning it will always have 9 rows and 9 columns.
Each cell of the board contains a digit from 1 to 9 or a dot ('.') to represent an empty cell.
The input is guaranteed to be a 9x9 board.

Now that we have a clear understanding of the problem, let’s explore the solution.

Efficient Solution with Hash Sets

To efficiently solve this problem, we can use three sets (or hash sets) for each of the following:

Rows
Columns
3×3 Sub-grids

We’ll iterate through each cell in the Sudoku board and check if it violates any of the Sudoku rules.

If it does, we return false immediately. Otherwise, we continue checking the next cells.

1. Rows and Columns

We’ll use hash sets to keep track of the digits we’ve seen in each row and column.

If we encounter a duplicate digit in a row or column, we return false. Otherwise, we add the digit to the respective row and column hash sets.

2. 3×3 Sub-grids

Handling the 3x3 sub-grids are a bit more complex.

To determine which sub-grid a cell belongs to, we’ll calculate its row and column indices divided by 3 (integer division).

This calculation will give us unique identifiers for each sub-grid.

For example, (4, 4) will map to sub-grid (1, 1), and (8, 8) will map to sub-grid (2, 2).

We’ll use a hash map where the keys are pairs of (row_index // 3, column_index // 3) and the values are hash sets to store the digits encountered in each sub-grid.

If we find a duplicate digit in a sub-grid, we return false.

By checking the rows, columns, and sub-grids in this way, we can efficiently determine if the Sudoku board is valid.

Valid Sudoku LeetCode Problem Python Solution

Now, let’s implement this solution in Python:

View on GitHub ➹

def isValidSudoku(self, board: List[List[str]]) -> bool:
    # Initialize hash sets for rows, columns, and sub-grids
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    subgrids = {(i // 3, j // 3): set() for i in range(9) for j in range(9)}

    for i in range(9):
        for j in range(9):
            cell = board[i][j]

            if cell == '.':
                continue

            # Check row
            if cell in rows[i]:
                return False
            rows[i].add(cell)

            # Check column
            if cell in cols[j]:
                return False
            cols[j].add(cell)

            # Check sub-grid
            subgrid = subgrids[(i // 3, j // 3)]
            if cell in subgrid:
                return False
            subgrid.add(cell)

    return True

This solution runs in O(1) time complexity because the size of the Sudoku board is fixed (9x9), and the nested loops iterate through the cells once.

The space complexity is also O(1) as we use fixed-size data structures for rows, columns, and sub-grids.

Time and Space Complexity

Time Complexity: O(1) – Since the size of the Sudoku board is fixed (9x9), our algorithm’s time complexity is constant.
Space Complexity: O(1) – Our space complexity is also constant because we use fixed-size data structures (hash sets) for rows, columns, and sub-grids.

Conclusion

In this blog post, we tackled the Valid Sudoku problem from LeetCode.

We implemented an efficient solution using hash sets to check the validity of a given Sudoku board.

By following the Sudoku rules for rows, columns, and 3x3 sub-grids, we were able to determine whether the board was valid or not.

Remember that this solution only validates the board based on the rules; it does not solve the Sudoku puzzle.

If you found this explanation helpful, please consider sharing and commenting.

Solve on LeetCode now.

Solving coding problems and understanding algorithmic concepts can be both fun and challenging, and we’re here to help you on your coding journey.