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