Valid Sudoku Board Coding Interview Question | Skilled.dev
Interview Question

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.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓
6 4
5 1 8
4 3
2
41 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:

  1. The board must be a square of k x k, and it must be composed of j x j size sub-squares.
  2. Rows: inside a given row, a value 1-k cannot appear more than once
  3. Columns: inside a given column, a value 1-k cannot appear more than once
  4. 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 valid and do not care if it is solvable. 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

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

  2. You can check for a valid board shape in constant time and space O(1).

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

  4. This question has some edge cases. Have you considered any in your solution?

  5. Does your solution ensure the board is square?

  6. Does your solution ensure the sub-squares are square?

  7. Does your solution check for an empty board input (n=0)?

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