Valid Sudoku: Checking Rows, Columns, and 3×3 Boxes

Sudoku is a classic 9×9 puzzle where each row, column, and 3×3 box must contain the digits 1 through 9 without repetition. In this problem, we are not asked to solve the Sudoku board. Instead, we only need to check whether the current board is valid.

The board contains digits from 1 to 9 and empty cells represented by ".".

Problem

Given a 9×9 Sudoku board, return True if the board is valid. Otherwise, return False.

A board is valid if:

  • Each row contains no duplicate digits.
  • Each column contains no duplicate digits.
  • Each 3×3 sub-box contains no duplicate digits.

Empty cells should be ignored.

Approach

To validate the board, I used three hash maps:

row = defaultdict(list)
col = defaultdict(list)
square = defaultdict(list)

These store the numbers already seen in each row, column, and 3×3 square.

For every cell in the board, I check whether the current value already exists in:

row[r]
col[c]
square[r // 3, c // 3]

The expression r // 3, c // 3 helps identify which 3×3 square the cell belongs to.

For example:

  • Rows 0–2 and columns 0–2 belong to square (0, 0)
  • Rows 0–2 and columns 3–5 belong to square (0, 1)
  • Rows 3–5 and columns 3–5 belong to square (1, 1)

If the value is already present in any of these places, the board is invalid, so we immediately return False.

If the cell is ".", we skip it because empty cells do not affect validity.

Solution

from collections import defaultdict
from typing import List

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = defaultdict(list)
        col = defaultdict(list)
        square = defaultdict(list)

        for r in range(9):
            for c in range(9):
                if (board[r][c] in row[r]
                    or board[r][c] in col[c]
                    or board[r][c] in square[r // 3, c // 3]):
                        return False
                
                if board[r][c] == ".":
                    continue
                
                row[r].append(board[r][c])
                col[c].append(board[r][c])
                square[r // 3, c // 3].append(board[r][c])

        return True

Walkthrough

For each cell, we do the following:

  1. Check if the value already exists in the current row.
  2. Check if the value already exists in the current column.
  3. Check if the value already exists in the current 3×3 square.
  4. If the value is ".", skip it.
  5. Otherwise, add the value to the row, column, and square trackers.

This makes it easy to catch duplicates as soon as they appear.

Complexity

The board size is always 9×9, so technically the runtime is constant. But in general terms:

Time Complexity: O(9 × 9), which is O(1) for a fixed Sudoku board.

Space Complexity: O(9 × 9), also treated as O(1) because the board size is fixed.

Note

One small improvement would be to check for "." before checking duplicates. This avoids checking empty cells inside the hash maps:

if board[r][c] == ".":
    continue

Then the duplicate check can happen only for actual digits.

Final Thoughts

This solution works by keeping track of numbers we have already seen in each row, column, and 3×3 square. The moment we find a duplicate, we know the Sudoku board is invalid. Using hash maps makes the logic simple and efficient.