Problem 8 - Valid Sudoku

Explore our archive for previous posts.

Question

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

Constraints:

• board.length == 9

• board[i].length == 9

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

Approach

The approach is to check the validity of the Sudoku board by validating each row, column, and 3x3 sub-grid separately.

In the isValidSudoku method, you call three helper methods: isRowValid, isColumnValid, and isBlockValid.

• isRowValid iterates over each row and uses a boolean array to track visited digits. It checks if a digit has already been visited and returns false if it has.

• isColumnValid iterates over each column and uses a boolean array to track visited digits. It checks if a digit has already been visited and returns false if it has.

• isBlockValid iterates over each 3x3 sub-grid and uses a boolean array to track visited digits. It checks if a digit has already been visited and returns false if it has.

If all three helper methods return true, the Sudoku board is considered valid, and the isValidSudoku method returns true.

Solution

Solve it here

class Solution {
    public boolean isValidSudoku(char[][] board) {
        return isRowValid(board) && isColumnValid(board) && isBlockValid(board);
    }
    
    // Check rows
    private boolean isRowValid(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            boolean[] visited = new boolean[10];
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (visited[board[i][j] - '0']) {
                    return false;
                }
                visited[board[i][j] - '0'] = true;
            }
        }
        return true;
    }
    
    // Check columns
    private boolean isColumnValid(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            boolean[] visited = new boolean[10];
            for (int j = 0; j < board[0].length; j++) {
                if (board[j][i] == '.') {
                    continue;
                }
                if (visited[board[j][i] - '0']) {
                    return false;
                }
                visited[board[j][i] - '0'] = true;
            }
        }
        return true;
    }
    
    // Check 3*3 sub-grids
    private boolean isBlockValid(char[][] board) {
        for (int block = 0; block < 9; block++) {
            boolean[] visited = new boolean[10];
            for (int i = block / 3 * 3; i < block /3 * 3 + 3; i++) {
                for (int j = block % 3 * 3; j < block % 3 * 3 + 3; j++) {
                    if (board[j][i] == '.') {
                    continue;
                    }
                    if (visited[board[j][i] - '0']) {
                        return false;
                    }
                    visited[board[j][i] - '0'] = true;
                }
            }
        }
        return true;
    }
}

Time and space complexity

Time Complexity: The time complexity of the solution is O(1) because the size of the Sudoku board is fixed (always 9x9) and does not depend on the input size. The solution iterates over the board three times: once for validating rows, once for validating columns, and once for validating sub-grids. Each iteration takes constant time, so the overall time complexity remains constant.

Space Complexity: The space complexity is also O(1) because the space used by the solution does not grow with the input size. The solution uses boolean arrays of size 10 (one for each digit from 1 to 9) to track visited digits. Again, the size of these arrays is fixed and does not depend on the input size, resulting in constant space complexity.