# Valid Sudoku Board

## Course launching September 2020

**Follow me on YouTube** for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

6 | 4 | |||||||

5 | 1 | 8 | ||||||

4 | 3 | |||||||

2 | ||||||||

4 | 1 | 8 | 9 | |||||

7 | ||||||||

6 | 1 |

**This problem has a lot of detail, so take a breath and walk through it step-by-step. If this is too complex to solve now, come back after you level up and work through more of the course.**

Given a Sudoku board that is either partially or completely filled, determine if it is a valid board based on the numbers that are in each cell. A valid Sudoku board means there are no duplicate integers within a given row, column, or sub-square.

Thereâ€™s a catch - we want our Sudoku validator to work for *any* `k x k`

size board, not just the standard `9 x 9`

board.

The problem input will be a 2-dimensional array that corresponds to the rows and columns of the board.
The values of the array will be `0-k`

where `0`

means it is an empty cell and `1-k`

are values in a cell.

To be valid, the board must be a square of `n = k x k`

where `k`

is the length of each side and `n`

is the total number of cells.
Let's also call `j = sqrt(k)`

- a valid board must consist of sub-squares that are `j x j`

.

A standard `9 x 9`

Sudoku board would have `n = 81`

cells, `k = 9`

row and column length, and each sub-square would have a row and column length of `j = 3`

.

A valid board must meet the following criteria:

- The board must be a square of
`k x k`

, and it must be composed of`j x j`

size sub-squares. - Rows: inside a given row, a value
`1-k`

cannot appear more than once - Columns: inside a given column, a value
`1-k`

cannot appear more than once - Sub-squares: inside a given sub-square, a value
`1-k`

cannot appear more than once

**Write a function isValidSudokuBoard which returns a boolean indicating if the board is valid.**

Keep in mind that we only want to determine that the board is

validand do not care if it issolvable. To be considered valid, the input only needs to match the outlined criteria. We do not care if the board is mathematically solvable and could reach a completed state from the initial board.

Example 1:

```
// Input
const board = [
[0, 0, 6, 0, 0, 4, 0, 0, 0],
[5, 0, 0, 1, 0, 0, 0, 0, 8],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 4, 0, 0, 0, 3, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 2, 0, 0, 0, 0, 0, 0],
[4, 1, 0, 8, 0, 0, 9, 0, 0],
[7, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 6, 0, 0, 1],
];
// Output
isValidSudokuBoard(board); // true
```

Example 2:

```
// Input
const board = [
[0, 2, 0],
[1, 0, 0],
];
// Output
// The shape of the board is invalid.
isValidSudokuBoard(board); // false
```

Example 3:

```
// Input
const board = [
[0, 2, 0, 4],
[1, 0, 0, 0],
[0, 0, 0, 0],
[0, 3, 0, 4],
];
// Output
// In the last column we have the number 4 duplicated.
isValidSudokuBoard(board); // false
```

### Validate My Answer

View your solution in 2 parts - does it handle checking for a valid board shape and also valid cell content?

You can check for a valid board shape in constant time and space

*O(1)*.You can check for valid cell content in linear time and space

*O(n)*.This question has some edge cases. Have you considered any in your solution?

Does your solution ensure the board is square?

Does your solution ensure the sub-squares are square?

Does your solution check for an empty board input (

`n=0`

)?Does your solution work if all the cells are empty (all values are

`0`

)?