Valid Sudoku

Medium#36three sets

You get a 9 × 9 sudoku board, partly filled. Check that it breaks no rule: a digit may not repeat in a row, in a column or in any of the nine 3 × 3 boxes. You do not have to solve it. Our board has 17 digits, and the answer is false: two 7s share the bottom-right box, though their rows and columns differ.

36 Valid SudokuWalkthrough · 1×

Example: our board of 17 digits. The frame shows what the current digit is checked against: its row and column, then its box.

00112233445566778853761984283657297
not checked yetcurrent digitin the setsthe same digit

Nine empty sets for the rows, nine for the columns and nine for the boxes

01/86
restart · back · play · step
Speed
1function isValidSudoku(board):
2 rows, cols, boxes = 9 empty sets each
3 for each digit d at (r, c) on board:
4 b = (r / 3) * 3 + c / 3 // round down
5 if d in rows[r] or d in cols[c]:
6 return false
7 if d in boxes[b]:
8 return false
9 add d to rows[r], cols[c], boxes[b]
10 return true
state
r
–
c
–
d
–
b
–
rows[r]
–
cols[c]
–
boxes[b]
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Each row, column and box keeps a set of the digits already in it. A set answers "is this digit here?" at once, so a digit is checked against all three without looking over the board again.
  2. The box comes from the row and the column: r / 3 and c / 3 rounded down give the box row and the box column, 0 to 2, and (r / 3) × 3 + c / 3 numbers the boxes 0 to 8, row by row.
  3. One pass is enough: a repeat is caught when its second copy comes up, because the first one is already in the set. Empty cells take no part.

Complexity

Time O(1): the board is always 81 cells, and each digit is looked up in three sets once; for an n × n board it would be O(n²). Memory O(1) for the same reason: 27 sets of at most 9 digits.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.