#36 Valid Sudoku
the problem
In plain words
Decide whether a partially filled 9×9 Sudoku board is valid: no digit 1–9 repeats in any row, any column, or any of the nine 3×3 boxes. Empty cells are '.'. The board need not be solvable.
in board = ["53..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"] (each string is one row)
out true
in The same board, but the first row is "83..7...."
out false
Two 8s in the top-left box.
- board is 9×9
- board[i][j] is a digit 1–9 or '.'
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternHash lookup (seen before?)Bitmask as a set
The box of cell (r, c) is (r / 3) * 3 + c / 3. With that formula, one pass checks rows, columns and boxes together.
solutions
From brute force to optimal
For each i, use three fresh sets for row i, column i and box i.
- For i in 0..8: new row/col/box sets.
- For j in 0..8: read row cell, column cell and box cell; reject any repeat.
Fixed board: 3 × 81 checks. For an n×n board it's O(n²).
Three sets of at most 9 digits at a time.
class Solution { public boolean isValidSudoku(char[][] board) { for (int i = 0; i < 9; i++) { Set<Character> row = new HashSet<>(), col = new HashSet<>(), box = new HashSet<>(); for (int j = 0; j < 9; j++) { char r = board[i][j]; // row i char c = board[j][i]; // column i char b = board[3 * (i / 3) + j / 3][3 * (i % 3) + j % 3]; // box i, cell j if (r != '.' && !row.add(r)) return false; if (c != '.' && !col.add(c)) return false; if (b != '.' && !box.add(b)) return false; } } return true; }}Record facts like "5 in row 0", "5 in col 3", "5 in box 0-1"; add fails on any repeat.
- For each filled cell, add three strings.
- Any add returns false → invalid.
81 cells × 3 adds (strings make the constant larger).
At most 243 strings.
class Solution { public boolean isValidSudoku(char[][] board) { Set<String> seen = new HashSet<>(); for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { char d = board[r][c]; if (d == '.') continue; // add() returns false if this exact fact was already recorded if (!seen.add(d + " in row " + r) || !seen.add(d + " in col " + c) || !seen.add(d + " in box " + (r / 3) + "-" + (c / 3))) return false; } } return true; }}An int's bits 1–9 mark which digits are used: a tiny, allocation-free hash set.
- bit = 1 << digit.
- If rows[r], cols[c] or boxes[b] already has the bit → false.
- Otherwise OR the bit in.
81 cells with constant bit operations.
27 ints.
class Solution { public boolean isValidSudoku(char[][] board) { int[] rows = new int[9], cols = new int[9], boxes = new int[9]; // bit d set = digit d seen for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { if (board[r][c] == '.') continue; int bit = 1 << (board[r][c] - '0'); int b = (r / 3) * 3 + c / 3; // box index 0..8, left-to-right, top-to-bottom if ((rows[r] & bit) != 0 || (cols[c] & bit) != 0 || (boxes[b] & bit) != 0) return false; rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit; } } return true; }}in the room
How to say it in the interview
talk track
- Derive the box index formula on the whiteboard with two example cells.
- Mention that validity ≠ solvability: you only check the filled cells.
traps
- Writing the box index as
r / 3 + c / 3— boxes (0, 1) and (1, 0) then collide. Use(r / 3) * 3 + c / 3. - Forgetting to skip '.' cells, so the empty marker counts as a repeated digit.
- Trying to solve the board — you only check the filled cells for repeats.
what they ask next
Follow-ups
Sudoku Solver (LC 37)?
Backtracking, using these same row/column/box masks to test each placement in O(1).
before you submit
Edge cases to test
- An empty board ('.' everywhere) → true.
- A repeat only inside one box, sharing no row or column.
- Valid does not mean solvable — only the filled cells are checked.
practise next
Similar problems
- #217Contains DuplicateEasyin Hashing
- #51N-QueensHardin Backtracking