36. Valid Sudoku - Explanation

Description

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

Each row must contain the digits 1-9 without duplicates.
Each column must contain the digits 1-9 without duplicates.
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 '.'.

Recommended Time & Space Complexity

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.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

A valid Sudoku board must follow three rules:

Each row can contain digits 1–9 at most once.
Each column can contain digits 1–9 at most once.
Each 3×3 box can contain digits 1–9 at most once.

We can directly check all these conditions one by one.
For every row, every column, and every 3×3 box, we keep a set of seen digits and make sure no number appears twice.
If we ever find a duplicate in any of these three checks, the board is invalid.

Algorithm

Check all rows:
- For each row index row from 0 to 8:
  - Create an empty set seen.
  - For each column index i from 0 to 8:
    - Skip if the cell is ".".
    - If the value is already in seen, return False.
    - Otherwise, add it to seen.
Check all columns:
- For each column index col from 0 to 8:
  - Create an empty set seen.
  - For each row index i from 0 to 8:
    - Skip if the cell is ".".
    - If the value is already in seen, return False.
    - Otherwise, add it to seen.
Check all 3×3 boxes:
- Number the 3×3 boxes from 0 to 8.
- For each square:
  - Create an empty set seen.
  - For i in 0..2 and j in 0..2:
    - Compute:
      - row = (square // 3) * 3 + i
      - col = (square % 3) * 3 + j
    - Skip if the cell is ".".
    - If the value is already in seen, return False.
    - Otherwise, add it to seen.
If all rows, columns, and 3×3 boxes pass these checks without duplicates, return True.

class Solution:
    def isValidSudoku(self, 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 & Space Complexity

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

2. Hash Set (One Pass)

Intuition

Instead of checking rows, columns, and 3×3 boxes separately, we can validate the entire Sudoku board in one single pass.
For each cell, we check whether the digit has already appeared in:

the same row
the same column
the same 3×3 box

We track these using three hash sets:

rows[r] keeps digits seen in row r
cols[c] keeps digits seen in column c
squares[(r // 3, c // 3)] keeps digits in the 3×3 box

If a digit appears again in any of these places, the board is invalid.

Algorithm

Create three hash maps of sets:
- rows to track digits in each row
- cols to track digits in each column
- squares to track digits in each 3×3 sub-box, keyed by (r // 3, c // 3)
Loop through every cell in the board:
- Skip the cell if it contains ".".
- Let val be the digit in the cell.
- If val is already in:
  - rows[r] → duplicate in the row
  - cols[c] → duplicate in the column
  - squares[(r // 3, c // 3)] → duplicate in the 3×3 box
    Then return False.
Otherwise, add the digit to all three sets:
- rows[r]
- cols[c]
- squares[(r // 3, c // 3)]
If the whole board is scanned without detecting duplicates, return True.

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = defaultdict(set)
        rows = defaultdict(set)
        squares = defaultdict(set)

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                if ( board[r][c] in rows[r]
                    or board[r][c] in cols[c]
                    or board[r][c] in squares[(r // 3, c // 3)]):
                    return False

                cols[c].add(board[r][c])
                rows[r].add(board[r][c])
                squares[(r // 3, c // 3)].add(board[r][c])

        return True

Time & Space Complexity

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

3. Bitmask

Intuition

Every digit from 1 to 9 can be represented using a single bit in an integer.
For example, digit 1 uses bit 0, digit 2 uses bit 1, …, digit 9 uses bit 8.
This means we can track which digits have appeared in a row, column, or 3×3 box using just one integer per row/column/box instead of a hash set.

When we encounter a digit, we compute its bit position and check:

if that bit is already set in the row → duplicate in row
if that bit is already set in the column → duplicate in column
if that bit is already set in the box → duplicate in box

If none of these checks fail, we “turn on” that bit to mark the digit as seen.
This approach is both memory efficient and fast.

Algorithm

Create three arrays of size 9:
- rows[i] stores bits for digits seen in row i
- cols[i] stores bits for digits seen in column i
- squares[i] stores bits for digits seen in 3×3 box i
Loop through each cell (r, c) of the board:
- Skip if the cell contains ".".
- Convert the digit to a bit index: val = int(board[r][c]) - 1.
- Compute the mask: mask = 1 << val.
Check for duplicates:
- If mask is already set in rows[r], return False.
- If mask is already set in cols[c], return False.
- If mask is already set in squares[(r // 3) * 3 + (c // 3)], return False.
Mark the digit as seen:
- rows[r] |= mask
- cols[c] |= mask
- squares[(r // 3) * 3 + (c // 3)] |= mask
If all cells are processed without conflicts, return True.

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [0] * 9
        cols = [0] * 9
        squares = [0] * 9

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue

                val = int(board[r][c]) - 1
                if (1 << val) & rows[r]:
                    return False
                if (1 << val) & cols[c]:
                    return False
                if (1 << val) & squares[(r // 3) * 3 + (c // 3)]:
                    return False

                rows[r] |= (1 << val)
                cols[c] |= (1 << val)
                squares[(r // 3) * 3 + (c // 3)] |= (1 << val)

        return True

Time & Space Complexity

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