Valid Sudoku

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.
  2. Each column must contain the digits 1-9 without repetition.
  3. 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
Input: board = 
[["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"]]
Output: true

Example 2:

Input: board = 
[["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"]]
Output: false
Explanation: 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.

Constraints:

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

Solution

Approach 1:

Java
class Solution {
    public boolean isValidSudoku(char[][] board) {
        Map<Integer,Set<Character>> rowMap = new HashMap<Integer, Set<Character>>();
        Map<Integer, Set<Character>> columnMap = new HashMap<Integer, Set<Character>>();
        Map<Integer, Set<Character>> boxMap = new HashMap<Integer, Set<Character>>();

        for(int i = 0; i< 9 ; i++) {
            for(int j = 0; j< 9; j++) {
                char ch = board[i][j];
                int b = (i/3)*3 + (j/3);
                if(ch != '.') {
                    //Row Duplicacy check
                    if(!rowMap.containsKey(i)) rowMap.put(i, new HashSet<Character>(Set.of(ch)));
                    else if(rowMap.get(i).contains(ch)) return false;
                    else rowMap.get(i).add(ch);

                    // Column Duplicacy check
                    if(!columnMap.containsKey(j)) columnMap.put(j, new HashSet<Character>(Set.of(ch)));
                    else if(columnMap.get(j).contains(ch)) return false;
                    else columnMap.get(j).add(ch);

                    // Box check
                    if(!boxMap.containsKey(b)) boxMap.put(b, new HashSet<Character>(Set.of(ch)));
                    else if(boxMap.get(b).contains(ch)) return false;
                    else boxMap.get(b).add(ch);

                }

            }
        }
        return true;
    }
}
Agnibha Chandra

Approach 2:

Java
class Solution {

    public boolean isValidSudoku(char[][] board) {
        int rows = board.length;
        int cols = board[0].length;

        Set<Character> rowSet = null;
        Set<Character> colSet = null;

        //check for rows
        for (int i = 0; i < rows; i++) {
            rowSet = new HashSet<>();
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (rowSet.contains(board[i][j])) {
                    return false;
                }
                rowSet.add(board[i][j]);
            }
        }

        //check for cols
        for (int i = 0; i < cols; i++) {
            colSet = new HashSet<>();
            for (int j = 0; j < rows; j++) {
                if (board[j][i] == '.') {
                    continue;
                }
                if (colSet.contains(board[j][i])) {
                    return false;
                }

                colSet.add(board[j][i]);
            }
        }

        //block
        for (int i = 0; i < rows; i = i + 3) {
            for (int j = 0; j < cols; j = j + 3) {
                if (!checkBlock(i, j, board)) {
                    return false;
                }
            }
        }

        return true;
    }

    public boolean checkBlock(int idxI, int idxJ, char[][] board) {
        Set<Character> blockSet = new HashSet<>();
        int rows = idxI + 3;
        int cols = idxJ + 3;
        for (int i = idxI; i < rows; i++) {
            for (int j = idxJ; j < cols; j++) {
                if (board[i][j] == '.') {
                    continue;
                }

                if (blockSet.contains(board[i][j])) {
                    return false;
                }

                blockSet.add(board[i][j]);
            }
        }

        return true;
    }
}
Agnibha Chandra