Valid Sudoku
Verify a partially filled Sudoku board obeys row, column, and 3x3 box rules.
4 min read
hash-set matrix validation
Problem#
Given a 9x9 Sudoku board ('.' for empty cells), return true if every row, every column, and every 3x3 sub-box contains no duplicate digits 1-9. Empty cells don’t impose constraints.
Examples#
- Standard valid board →
true. - A board with two
'8's in column 0 →false.
Constraints#
- Board is 9x9, characters are
'1'..'9'or'.'.
Hints#
Hint
Three sets of seen digits: per row, per column, per 3x3 box. Box index =
(r/3)*3 + c/3. Approach#
For each filled cell, encode the value with a row tag, column tag, and box tag, and try to insert each into a single unordered_set<string>. Any collision means a violation.
Solution#
class Solution {public: bool isValidSudoku(vector<vector<char>>& board) { bool row[9][9] = {}, col[9][9] = {}, box[9][9] = {}; for (int r = 0; r < 9; ++r) { for (int c = 0; c < 9; ++c) { if (board[r][c] == '.') continue; int d = board[r][c] - '1'; int b = (r / 3) * 3 + c / 3; if (row[r][d] || col[c][d] || box[b][d]) return false; row[r][d] = col[c][d] = box[b][d] = true; } } return true; }};func isValidSudoku(board [][]byte) bool { var row, col, box [9][9]bool for r := 0; r < 9; r++ { for c := 0; c < 9; c++ { if board[r][c] == '.' { continue } d := int(board[r][c] - '1') b := (r/3)*3 + c/3 if row[r][d] || col[c][d] || box[b][d] { return false } row[r][d] = true col[c][d] = true box[b][d] = true } } return true}from typing import List
class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: row = [[False] * 9 for _ in range(9)] col = [[False] * 9 for _ in range(9)] box = [[False] * 9 for _ in range(9)] for r in range(9): for c in range(9): if board[r][c] == '.': continue d = int(board[r][c]) - 1 b = (r // 3) * 3 + c // 3 if row[r][d] or col[c][d] or box[b][d]: return False row[r][d] = col[c][d] = box[b][d] = True return Truefunction isValidSudoku(board) { const row = Array.from({ length: 9 }, () => new Array(9).fill(false)); const col = Array.from({ length: 9 }, () => new Array(9).fill(false)); const box = Array.from({ length: 9 }, () => new Array(9).fill(false)); for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { if (board[r][c] === '.') continue; const d = board[r][c].charCodeAt(0) - '1'.charCodeAt(0); const b = Math.floor(r / 3) * 3 + Math.floor(c / 3); if (row[r][d] || col[c][d] || box[b][d]) return false; row[r][d] = col[c][d] = box[b][d] = true; } } return true;}class Solution { public boolean isValidSudoku(char[][] board) { boolean[][] row = new boolean[9][9]; boolean[][] col = new boolean[9][9]; boolean[][] box = new boolean[9][9]; for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { if (board[r][c] == '.') continue; int d = board[r][c] - '1'; int b = (r / 3) * 3 + c / 3; if (row[r][d] || col[c][d] || box[b][d]) return false; row[r][d] = col[c][d] = box[b][d] = true; } } return true; }}function isValidSudoku(board: string[][]): boolean { const row: boolean[][] = Array.from({ length: 9 }, () => new Array(9).fill(false)); const col: boolean[][] = Array.from({ length: 9 }, () => new Array(9).fill(false)); const box: boolean[][] = Array.from({ length: 9 }, () => new Array(9).fill(false)); for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { if (board[r][c] === '.') continue; const d = board[r][c].charCodeAt(0) - '1'.charCodeAt(0); const b = Math.floor(r / 3) * 3 + Math.floor(c / 3); if (row[r][d] || col[c][d] || box[b][d]) return false; row[r][d] = col[c][d] = box[b][d] = true; } } return true;}Editorial#
Fixed bool[9][9] triples are faster than hash sets here — direct array indexing beats hashing for a 81-cell board. Box index (r/3)*3 + c/3 maps any (r, c) to its 3x3 region’s id in [0, 9).
Complexity#
- Time: O(1) — the board has a fixed size.
- Space: O(1).
Concept revision#
Related#