Valid Sudoku

How it works

Scan the board once and keep the digits already seen in each row, column, and 3×3 box. A filled cell is valid only if its digit is absent from all three sets. Check for a duplicate before adding the digit, so a cell never conflicts with itself.

In Python, collections.defaultdict(set) creates an empty set when a row, column, or box is first accessed. rows[r] tracks row r, cols[c] tracks column c, and squares[(r // 3, c // 3)] tracks the box. Integer division groups indices 0–2, 3–5, and 6–8 into box coordinates 0, 1, and 2. For example, cells (3, 6) and (5, 8) share box key (1, 2). The C++ example uses the same sets with the box key {r / 3, c / 3}.

Steps

1. Create the rows, cols, and squares maps of sets.
2. Visit each cell (r, c) in the 9×9 board. Skip ".", which represents an empty cell.
3. If board[r][c] is already in rows[r], cols[c], or squares[(r // 3, c // 3)], return False.
4. Otherwise, add the digit to all three sets and continue.
5. Return True after scanning the entire board without a duplicate.

Complexity

For this fixed 9×9 board, time and auxiliary space are O(1): visit at most 81 cells and store each filled digit in three sets. If generalized to an n×n board, expected time and auxiliary space are O(n²) with constant-time hash-set operations. The C++ box map has at most nine keys here; a generalized ordered map would add a logarithmic lookup factor.

Things to watch for

• Skip empty cells before checking or inserting; multiple "." cells are allowed.
• Use integer division for both box coordinates. r // 3 + c // 3 can merge different boxes into the same key.
• Check all three sets before inserting the current digit.
• This validates the filled cells; it does not solve the puzzle or determine whether it can be completed.
• The board is read without modifying it.

from typing import List
import collections

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        squares = collections.defaultdict(set)  # key = (r // 3, c // 3)

        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

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_map<int, unordered_set<char>> rows, cols;
        map<pair<int, int>, unordered_set<char>> squares;

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') continue;

                pair<int, int> squareKey = {r / 3, c / 3};

                if (rows[r].count(board[r][c]) || cols[c].count(board[r][c]) || squares[squareKey].count(board[r][c])) {
                    return false;
                }

                rows[r].insert(board[r][c]);
                cols[c].insert(board[r][c]);
                squares[squareKey].insert(board[r][c]);
            }
        }
        return true;
    }
};