0036 - Valid Sudoku

0036 - 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.

Examples

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

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 '.'.

Java Solution

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int maxSize = 9;
        
        HashSet<Character>[] rows = new HashSet[maxSize];
        HashSet<Character>[] columns = new HashSet[maxSize];
        HashSet<Character>[] squares = new HashSet[maxSize];

        for(int i = 0; i < maxSize; i++) {
            rows[i] = new HashSet<Character>();
            columns[i] = new HashSet<Character>();
            squares[i] = new HashSet<Character>();
        }
        
        for(int row = 0; row < maxSize; row++) {
            for(int column = 0; column < maxSize; column++) {
                char value = board[row][column];
                if(value == '.') continue;
                
                if(rows[row].contains(value)) return false;
                rows[row].add(value);
                
                if(columns[column].contains(value)) return false;
                columns[column].add(value);
                
                int square =(row/3) * 3 + column / 3;
                if(squares[square].contains(value)) return false;
                squares[square].add(value);
            }
            
        }
        return true;
    }
}