Valid Sudoku

Problem Statement

You are given a a 9 x 9 Sudoku board board. A Sudoku board is valid if the following rules are followed:

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

Return true if the Sudoku board is valid, otherwise return false

Note: A board does not need to be full or be solvable to be valid.

Example 1:

# Input:
  board =
  [["1","2",".",".","3",".",".",".","."],
   ["4",".",".","5",".",".",".",".","."],
   [".","9","8",".",".",".",".",".","3"],
   ["5",".",".",".","6",".",".",".","4"],
   [".",".",".","8",".","3",".",".","5"],
   ["7",".",".",".","2",".",".",".","6"],
   [".",".",".",".",".",".","2",".","."],
   [".",".",".","4","1","9",".",".","8"],
   [".",".",".",".","8",".",".","7","9"]]
# Output: True

Example 2:

# Input:
  board =
  [["1","2",".",".","3",".",".",".","."],
   ["4",".",".","5",".",".",".",".","."],
   [".","9","1",".",".",".",".",".","3"],
   ["5",".",".",".","6",".",".",".","4"],
   [".",".",".","8",".","3",".",".","5"],
   ["7",".",".",".","2",".",".",".","6"],
   [".",".",".",".",".",".","2",".","."],
   [".",".",".","4","1","9",".",".","8"],
   [".",".",".",".","8",".",".","7","9"]]
# Output: False
# Explanation: There are two 1's in the top-left 3x3 sub-box.

Constraints:

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

You should aim for a solution as good or better than O(n^2) time and O(n^2) space, where n is the number of rows in the square grid.

You should aim for a solution as good or better than O(n^2) time and O(n^2) space, where n is the number of rows in the square grid.

Hint 1

Which data structure would you prefer to use for checking duplicates?

Hint 2

You can use a hash set for every row and column to check duplicates. But how can you efficiently check for the squares?

Hint 3

We can find the index of each square by the equation (row / 3) * 3 + (col / 3). Then we use hash set for O(1) lookups while inserting the number into its row, column and square it belongs to. We use separate hash maps for rows, columns, and squares.

Solution

Brute Force

def is_valid_sudoku(board: list[list[str]]) -> bool:
    for row in range(9):
        seen = set()
        for i in range(9):
            if board[row][i] == ".":
                continue
            if board[row][i] in seen:
                return False
            seen.add(board[row][i])


    for col in range(9):
        seen = set()
        for i in range(9):
            if board[i][col] == ".":
                continue
            if board[i][col] in seen:
                return False
            seen.add(board[i][col])


    for square in range(9):
        seen = set()
        for i in range(3):
            for j in range(3):
                row = (square // 3) * 3 + i
                col = (square % 3) * 3 + j
                if board[row][col] == ".":
                    continue
                if board[row][col] in seen:
                    return False
                seen.add(board[row][col])
    return True

Time complexity: O(n^2) Space complexity: O(n^2)