Validate a Sudoku Grid

medium matrix hash set

Problem

A partially-filled 9×9 Sudoku board is valid if every row, every column, and every 3×3 sub-box contains the digits 1–9 with no repeats; empty cells (denoted .) are ignored. Sweep every filled cell, ask three questions: have I seen this digit in row r? in column c? in box (r/3, c/3)? If any answer is yes, the board is invalid. Otherwise mark all three and continue.

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;
}

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