Valid Sudoku

medium matrix hash set

Problem

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.

Inputa board with 5 placed twice in row 0

Outputfalse

The second 5 trips the row-set check at the moment we visit it.

board (9 rows separated by ';', use '.' for empty)

def is_valid_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for r in range(9):
        for c in range(9):
            v = board[r][c]
            if v == '.':
                continue
            b = (r // 3) * 3 + (c // 3)
            if v in rows[r] or v in cols[c] or v in boxes[b]:
                return False
            rows[r].add(v); cols[c].add(v); boxes[b].add(v)
    return True

function isValidSudoku(board) {
  const rows = Array.from({ length: 9 }, () => new Set());
  const cols = Array.from({ length: 9 }, () => new Set());
  const boxes = Array.from({ length: 9 }, () => new Set());
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const v = board[r][c];
      if (v === '.') continue;
      const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
      if (rows[r].has(v) || cols[c].has(v) || boxes[b].has(v)) return false;
      rows[r].add(v); cols[c].add(v); boxes[b].add(v);
    }
  }
  return true;
}

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<Character>[] rows = new HashSet[9];
        Set<Character>[] cols = new HashSet[9];
        Set<Character>[] boxes = new HashSet[9];
        for (int i = 0; i < 9; i++) { rows[i] = new HashSet<>(); cols[i] = new HashSet<>(); boxes[i] = new HashSet<>(); }
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char v = board[r][c];
                if (v == '.') continue;
                int b = (r / 3) * 3 + (c / 3);
                if (rows[r].contains(v) || cols[c].contains(v) || boxes[b].contains(v)) return false;
                rows[r].add(v); cols[c].add(v); boxes[b].add(v);
            }
        }
        return true;
    }
}

bool isValidSudoku(vector<vector<char>>& board) {
    bool rows[9][9] = {}, cols[9][9] = {}, boxes[9][9] = {};
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] == '.') continue;
            int v = board[r][c] - '1';
            int b = (r / 3) * 3 + (c / 3);
            if (rows[r][v] || cols[c][v] || boxes[b][v]) return false;
            rows[r][v] = cols[c][v] = boxes[b][v] = true;
        }
    }
    return true;
}

Explanation

A Sudoku board is valid if no digit repeats inside any row, any column, or any 3×3 box. The trick is to remember what we have already seen using hash sets, one per row, per column, and per box.

We create rows, cols, and boxes — nine sets each — then sweep every cell once. Empty cells ('.') are skipped.

For a filled cell at row r, column c, its box index is b = (r // 3) * 3 + (c // 3). This neat formula maps the 9 boxes to numbers 0–8.

Before placing the digit we check all three sets: if it is already in rows[r], cols[c], or boxes[b], that is a repeat, so we return false. Otherwise we add it to all three and continue.

Example: a board with two 5s in row 0. The first 5 gets added to rows[0]; when we reach the second 5, the check v in rows[r] is true, so we immediately return false. If we finish the whole sweep with no clash, the board is valid.

Time: O(1) (81 cells) Space: O(1)