Valid Sudoku

Medium

Problem

Given a partially filled 9 × 9 board ("." for empty), return true if the filled cells break no rule: no repeated digit in any row, any column, or any of the nine 3 × 3 boxes. The board does not need to be solvable.

Example 1

Input:  a board where one row contains two 8s
Output: false

Test cases

Case 1

Input:    [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Expected: true

Case 2

Input:    [["8","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Expected: false

Case 3

Input:    [["1",".",".",".",".",".",".",".","."],[".","1",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."]]
Expected: false

Case 4

Input:    [[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."]]
Expected: true

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. One pass with sets per row, column and box

Time O(81) = O(1)Space O(1)

Box index is floor(r/3)*3 + floor(c/3). Reject a digit already seen in any of its three units.

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