Logo for ammarahmed.ca
Medium
May 24, 2025
#matrices
#math

36. Valid Sudoku

Problem

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
    1. Each column must contain the digits 1-9 without repetition.
      1. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

        Note:

        • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
          • Only the filled cells need to be validated according to the mentioned rules.

            Example 1:

            1Input: board = 2[["5","3",".",".","7",".",".",".","."] 3,["6",".",".","1","9","5",".",".","."] 4,[".","9","8",".",".",".",".","6","."] 5,["8",".",".",".","6",".",".",".","3"] 6,["4",".",".","8",".","3",".",".","1"] 7,["7",".",".",".","2",".",".",".","6"] 8,[".","6",".",".",".",".","2","8","."] 9,[".",".",".","4","1","9",".",".","5"] 10,[".",".",".",".","8",".",".","7","9"]] 11Output: true 12

            Example 2:

            1Input: board = 2[["8","3",".",".","7",".",".",".","."] 3,["6",".",".","1","9","5",".",".","."] 4,[".","9","8",".",".",".",".","6","."] 5,["8",".",".",".","6",".",".",".","3"] 6,["4",".",".","8",".","3",".",".","1"] 7,["7",".",".",".","2",".",".",".","6"] 8,[".","6",".",".",".",".","2","8","."] 9,[".",".",".","4","1","9",".",".","5"] 10,[".",".",".",".","8",".",".","7","9"]] 11Output: false 12Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid. 13

            Constraints:

            • board.length == 9
              • board[i].length == 9
                • board[i][j] is a digit 1-9 or '.'.

                  Approach

                  Basically, we want to check if there are duplicates in each row, column and subbox.

                  To check for duplicates, we can write a helper function that will use a hashmap technique to check for duplicates.

                  Checking rows and columns is straightforward, the complexity arises with checking the subboxes because we need to figure out how to iterate over them. To keep it simple, we can do 4 nested loops, the box row, the box column, the inner row, the inner column, then we can index the board with board[3 * box_row + row][3 * box_col + col]. Using this, we can create the array of values for the subbox and check for duplicates.

                  Complexity

                  Time: O(n)

                  Since we iterate over the rows, columns and subboxes separately, it's all O(n)

                  Space: O(n)

                  The only extra space we create is for the rows, columns and subboxes which all have size of 9. Technically, it's all constant but we'll give it O(n)

                  Solution

                  1func hasDuplicate(values []byte) bool { 2 seen := make(map[byte]bool) 3 for _, val := range values { 4 if val == '.' { 5 continue 6 } 7 if _, exists := seen[val]; exists { 8 return true 9 } 10 seen[val] = true 11 } 12 return false 13} 14func isValidSudoku(board [][]byte) bool { 15 n := len(board) 16 // Checking rows 17 for _, row := range board { 18 if hasDuplicate(row) { 19 return false 20 } 21 } 22 23 // Checking columns 24 for i := range n { 25 col := make([]byte, n) 26 for j := range n { 27 col[j] = board[j][i] 28 } 29 if hasDuplicate(col) { 30 return false 31 } 32 } 33 34 // Checking sub-boxes 35 for brow := range 3 { 36 for bcol := range 3 { 37 var values []byte 38 for row := range 3 { 39 for col := range 3 { 40 values = append(values, board[3 * brow + row][3 * bcol + col]) 41 } 42 } 43 if hasDuplicate(values) { 44 return false 45 } 46 } 47 } 48 49 return true 50} 51