DEV Community

Huzaifa Rasheed
Huzaifa Rasheed

Posted on

Valid Sudoku Algo - Leetcode

#algorithms #javascript #programming #career

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 };
Enter fullscreen mode Exit fullscreen mode

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

  1. 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
Enter fullscreen mode Exit fullscreen mode
  1. 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
Enter fullscreen mode Exit fullscreen mode
  1. 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
Enter fullscreen mode Exit fullscreen mode
  1. 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
Enter fullscreen mode Exit fullscreen mode

It may not be perfect, and can always be improved. Let me know your thoughts and thanks for reading.

Top comments (0)