By Long Luo
This article is the solution 2 Approaches: HashSet and Array of Problem 36. Valid Sudoku .
Here shows 2 Approaches to slove this problem: HashSet and Array .
HashSet
We can use a HashSet to record the number of occurrences of each number in each row, each column and each sub-box.
Traverse the Sudoku once, update the count in the HashMap during the traversal process, and determine whether the Sudoku board could be valid.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 public static boolean isValidSudoku (char [][] board) { Map<Integer, Set<Integer>> rowMap = new HashMap <>(); Map<Integer, Set<Integer>> colMap = new HashMap <>(); for (int i = 0 ; i < 9 ; i++) { rowMap.put(i, new HashSet <>()); colMap.put(i, new HashSet <>()); } for (int i = 0 ; i < 9 ; i++) { for (int j = 0 ; j < 9 ; j++) { char ch = board[i][j]; if (ch != '.' ) { int num = ch - '0' ; Set<Integer> rowSet = rowMap.get(i); if (!rowSet.add(num)) { return false ; } Set<Integer> colSet = colMap.get(j); if (!colSet.add(num)) { return false ; } } } } for (int subIdx = 0 ; subIdx < 9 ; subIdx++) { int subRow = 3 * (subIdx / 3 ); int subCol = 3 * (subIdx % 3 ); Set<Integer> grpSet = new HashSet <>(); for (int i = 0 ; i < 3 ; i++) { for (int j = 0 ; j < 3 ; j++) { char ch = board[subRow + i][subCol + j]; if (ch != '.' ) { int num = ch - '0' ; if (!grpSet.add(num)) { return false ; } } } } } return true ; }
This is version 1.0 code.
In fact, we can only traversal once. The index of each sub-box is 3 × ( i / 3 ) + j / 3 3 \times (i / 3) + j / 3 3 × ( i / 3 ) + j / 3 , so we can write better code.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 public static boolean isValidSudoku_better (char [][] board) { Map<Integer, Set<Integer>> rowMap = new HashMap <>(); Map<Integer, Set<Integer>> colMap = new HashMap <>(); Map<Integer, Set<Integer>> subMap = new HashMap <>(); for (int i = 0 ; i < 9 ; i++) { rowMap.put(i, new HashSet <>()); colMap.put(i, new HashSet <>()); subMap.put(i, new HashSet <>()); } for (int i = 0 ; i < 9 ; i++) { for (int j = 0 ; j < 9 ; j++) { char ch = board[i][j]; if (ch != '.' ) { int num = ch - '0' ; Set<Integer> rowSet = rowMap.get(i); if (!rowSet.add(num)) { return false ; } Set<Integer> colSet = colMap.get(j); if (!colSet.add(num)) { return false ; } int subIdx = 3 * (i / 3 ) + j / 3 ; Set<Integer> subSet = subMap.get(subIdx); if (!subSet.add(num)) { return false ; } } } } return true ; }
Analysis
Time Complexity : O ( 1 ) O(1) O ( 1 ) .
Space Complexity : O ( 1 ) O(1) O ( 1 ) .
Array
Since numbers in Sudoku range from 1 1 1 to 9 9 9 , we can use array instead of the HashMap for counting.
We create a 2D Array, the rows and columns which record the number of occurrences of each number in each row and column of Sudoku, and create a 3D Array subboxes to record the number of occurrences of each number in each sub-box.
If the count is greater than 1 1 1 , the Sudoku is not valid.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public static boolean isValidSudoku_array (char [][] board) { int [][] row = new int [9 ][9 ]; int [][] col = new int [9 ][9 ]; int [][][] subBox = new int [3 ][3 ][9 ]; for (int i = 0 ; i < 9 ; i++) { for (int j = 0 ; j < 9 ; j++) { char ch = board[i][j]; if (ch != '.' ) { int num = ch - '0' - 1 ; row[i][num]++; col[j][num]++; subBox[i / 3 ][j / 3 ][num]++; if (row[i][num] > 1 || col[j][num] > 1 || subBox[i / 3 ][j / 3 ][num] > 1 ) { return false ; } } } } return true ; }
Analysis
Time Complexity : O ( 1 ) O(1) O ( 1 ) .
Space Complexity : O ( 1 ) O(1) O ( 1 ) .
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions . 😉😃💗