Start learning free

LESSON 355 OF 667 · HASH TABLE

Valid Sudoku

Practice O(81)

You get a partly filled Sudoku board. It is a 9 x 9 grid. Each cell holds a digit from '1' to '9', or '.' if it is empty.

Return true if no digit is repeated so far, and false otherwise. A digit is repeated when it shows up twice:

  1. in one row,
  2. in one column,
  3. or in one 3 x 3 box.

Thick lines split the grid into nine 3 x 3 boxes. They come after rows 2 and 5 and after columns 2 and 5.

Check only the digits on the board. Empty cells don't matter. You don't solve the puzzle. A board can pass this check even if it has no solution.

Rows are counted from 0 at the top, columns from 0 at the left. In the examples, each line is one row of the board.

 

Example 1:

547 47968 1634 74 5 853 429 62341 3492

Input: board =
5..4.7...
47.9..68.
.1...6.34
....7.4..
.5.......
...8..5.3
....4.29.
62....341
.34.92...
Output: true
Explanation: No row, column or box holds the same digit twice.

Example 2:

Input: board =
5..4.7...
47.9..68.
.1...6.34
....7.4..
.5.....9.
...8..5.3
....4.29.
62....341
.34.92...
Output: false
Explanation: This is the board of Example 1 with one more 9.
The new 9 is in row 4, column 7.
Column 7 already has a 9, in row 6.

Example 3:

Input: board =
.......5.
.2.......
.........
1....8...
....6....
..1......
.........
......3..
.9.......
Output: false
Explanation: The two 1s are in different rows, 3 and 5.
They are in different columns, 0 and 2.
But they are in the same box: rows 3 to 5, columns 0 to 2.

 

Constraints:

  • The board always has 9 rows of 9 cells.
  • Every cell is a digit from '1' to '9' or '.'.

Note:

Your algorithm should look at each cell once and check it in constant time: O(81) time and O(81) extra space for the 81 cells. Scanning the row, the column and the box of every cell again would also work on a board this small, but it looks at each cell many times.

STEP 1 OF 11
    Ctrl + Enter to check