36. Valid Sudoku

Hello, reader 👋🏽 ! Welcome to day 53 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 36. Valid Sudoku.

🤔 Problem Statement

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits 1-9 without repetition.
- Each column must contain the digits 1-9 without repetition.
- Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note: The board does not be verified if it's solvable or not. It only needs to be check for validity using the above rules.

E.g.:

[["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"]]
=> true

[["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"]]
=> false

💬 Thought Process - Map and Set

To verify if the board is valid, we need to check three things:
1. Ensure in every row, all the numbers are unique.
2. Ensure in every col, all the numbers are unique.
3. Ensure in every grid, all the numbers are unique.
We can use a map and set to determine if the board is valid or not.
The map would contain the row, grid and column numbers as keys and the value would be a set containing all the values in the row, grid and column.
To save grid numbers we'll be using (i/3), (j/3) as keys where i represents row, and j represents col. Basically we would get (0,0), (0,1), (0,2) which would represent sub grids 0, 1 and 2 in row 0. Similarly in rows 1 and 2: (1,0), (1,1), (1,2) and (2,0), (2,1), (2,2).
But if you see the key values might not be unique. If we simply use row, and col numbers as keys, there can be repetitions. For e.g. key 0 could be for row, or col!
To differentiate, we can store keys as strings such that we save "row0", "col0", "grid00" which represents row 0, column 0, and sub-grid 0 in row 0.
At any point when we try to add values to the set for a grid, row or column and the insertion is not successful, this means that the value was already present in the set. Hence, we can return false as we found a duplicate.
Once we have iterated over the entire board we know we found no duplicates in any row, column or grid and can return true.
Also we need not consider empty cells with '.' and can ignore them while iterating the board.

👩🏽‍💻 Solution - Map and Set

Below is the code for the above explained approach.

class Solution {
  public boolean isValidSudoku(char[][] board) {
      Map<String, HashSet<Character>> map = new HashMap();

      for(int row = 0; row<9; row++) {
          for(int col = 0; col<9; col++) {
              char ch = board[row][col];
              if(ch == '.') continue;

              String grid = "grid" + (row/3) + (col/3);
              String rowKey = "row" + row;
              String colKey = "col" + col;

              if(!map.containsKey(rowKey)) {
                  map.put(rowKey, new HashSet());
              }
              if(!map.get(rowKey).add(ch)) return false;

              if(!map.containsKey(colKey)) {
                  map.put(colKey, new HashSet());
              }
              if(!map.get(colKey).add(ch)) return false;

              if(!map.containsKey(grid)) {
                  map.put(grid, new HashSet());
              }
              if(!map.get(grid).add(ch)) return false;
          }
      }

      return true;
  }
}

Time Complexity: O(9*9)
Space Complexity: O(9*9*9)

Since the board is only of 9x9 dimensions, the cost for time and the space are basically constant.
In the worst case we would have to iterate over all 81 cells and would need a map with 9 row keys each of whose set would contain 9 element. Similarly, 9 column keys with set occupying 9 elements and 9 grid keys with each set containing 9 values.

You can find the link to the GitHub repo for this question here: 36. Valid Sudoku.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

Bharati Subramanian