So the other day I was doing some leetcode and found the Valid Sudoku problem interesting. Also since I had not posted for a long time (missed it 😁), thought why not just write how I solved, so here it goes.
Algorithm (I followed)
1- Map over each row of the board, check if row has duplicate numbers
2- Map over each column of the board, check if column has duplicate numbers
3- Map over each row of the board, if that row is the start of a unique 3x3 matrix, then create three 3x3 matrices and check for duplicates
We can check for each test case in a single map
Implementation (JavaScript)
/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function (board) {
// map over each row
for (let row = 0; row < board.length; row++) {
// we will store and check for dup digits
const foundRowDigits = [];
const foundColDigits = [];
// map over each column
for (let col = 0; col < board.length; col++) {
const rowDigit = board[row][col]
if (rowDigit !== '.') { // we are ignoring periods '.'
// check duplicates in row
if (foundRowDigits.includes(rowDigit)) {
// oh uh, dup found -> invalid sudoku
return false
}
foundRowDigits.push(rowDigit) // store row digit for further comparison
}
const colDigit = board[col][row]
if (colDigit !== '.') { // we are ignoring periods '.'
// check duplicates in row
if (foundColDigits.includes(colDigit)) {
// oh uh, dup found -> invalid sudoku
return false
}
foundColDigits.push(colDigit) // store row digit for further comparison
}
}
if (row % 3 === 0) { // row is the start of 3 3x3 matrices
let threeByThreeGrid = [] // we will store grid values to check dups
let rowIndex = row
for (let colIndex = 0; colIndex < 9; colIndex += 3) {
// make 3x3 grid by taking a rowIndex and colIndex
for (let gridRowIndex = rowIndex; gridRowIndex < rowIndex + 3; gridRowIndex++) {
for (let gridColIndex = colIndex; gridColIndex < colIndex + 3; gridColIndex++) {
const digit = board[gridRowIndex][gridColIndex]
if (digit !== '.') { // we are ignoring periods '.'
// check if there are duplicates in a 3x3 matrix
if (threeByThreeGrid.includes(digit)) {
// oh uh, dup found -> invalid sudoku
return false
}
threeByThreeGrid.push(digit) // store row digit for further comparison
}
}
}
threeByThreeGrid = [] // reset the grid
}
}
}
return true // if above test cases passed then sudoku is valid
};
Time complexity
O(n^2) - We have 2 nested for loops. The 3x3 subgrids only work in certain cases so going for the worst case we have O(n^2)
Space complexity
O(1)
Test Cases
- A valid sudoku
const validSudoku = [
["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"]
]
console.log(isValidSudoku(validSudoku)) // true
- A sudoku with dups in row
const sudokuWithRowDups = [
["5", "3", ".", ".", "7", ".", ".", ".", "5"],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"]
]
console.log(isValidSudoku(sudokuWithRowDups)) // false
- A sudoku with dups in col
const sudokuWithColDups = [
["8", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"]
]
console.log(isValidSudoku(sudokuWithColDups)) // false
- A sudoku with dups in 3x3 matrices
const sudokuWith3x3GridDups = [
[".", ".", ".", ".", "5", ".", ".", "1", "."],
[".", "4", ".", "3", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", "3", ".", ".", "1"],
["8", ".", ".", ".", ".", ".", ".", "2", "."],
[".", ".", "2", ".", "7", ".", ".", ".", "."],
[".", "1", "5", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", "2", ".", ".", "."],
[".", "2", ".", "9", ".", ".", ".", ".", "."],
[".", ".", "4", ".", ".", ".", ".", ".", "."]
]
console.log(isValidSudoku(sudokuWith3x3GridDups)) // false
It may not be perfect, and can always be improved. Let me know your thoughts and thanks for reading.
Top comments (0)