Hide sidebar
leetcode/DSA courseSystem Design

Valid Sudoku

Valid Sudoku

2D MatrixHash Set
MediumLeetCode #36
30 min

Problem Statement

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 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

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.

Example

Example 1:
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

Solution

The most straightforward way to validate a Sudoku board is to iterate through it and check each row, column, and 3x3 square for duplicate numbers. We can use hash sets to efficiently keep track of the numbers we've seen.

A clever optimization is to perform all three checks (row, column, and 3x3 square) in a single pass. We can iterate from `i = 0` to `8`. In each iteration, `i` can represent the current row index, column index, and 3x3 box index simultaneously.

Algorithm Steps

  • Loop from `i = 0` to `8`. This outer loop will represent the row, column, and box number.
  • In each iteration, initialize three new hash sets: `horizontal`, `vertical`, and `square`.
  • Start an inner loop from `j = 0` to `8` to iterate through the cells of the current row, column, and box.
  • Check the `j`th cell of the `i`th row. If it's a duplicate in `horizontal`, return `false`.
  • Check the `j`th cell of the `i`th column. If it's a duplicate in `vertical`, return `false`.
  • Calculate the coordinates for the `j`th cell within the `i`th 3x3 box. If it's a duplicate in `square`, return `false`.
  • If the loops complete without returning, the board is valid. Return `true`.

Sudoku Validation

Progress1 / 1
Ready to validate.
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
Valid Sudoku

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        for i in range(9):
            horizontal = set()
            vertical = set()
            square = set()
            
            r = 3 * (i // 3)
            c = 3 * (i % 3)
            
            for j in range(9):
                # Check horizontal
                if board[i][j] != '.' and board[i][j] in horizontal:
                    return False
                horizontal.add(board[i][j])
                
                # Check vertical
                if board[j][i] != '.' and board[j][i] in vertical:
                    return False
                vertical.add(board[j][i])
                
                # Check 3x3 square
                box_val = board[r + j // 3][c + j % 3]
                if box_val != '.' and box_val in square:
                    return False
                square.add(box_val)
                
        return True