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

Approach: Three Passes with Hash Sets (Optimal Solution)

Algorithm

1. Validate all rows: each row must not contain duplicate digits
2. Validate all columns: each column must not contain duplicate digits
3. Validate all nine 3 x 3 sub-boxes: each box must not contain duplicate digits
4. Skip cells containing '.'

Time & Space Complexity

• Time Complexity: O(1) - the board is always 9 x 9, so the work is constant
• Space Complexity: O(1) - only fixed-size hash sets are used

Java Implementation

import java.util.HashSet;
import java.util.Set;

public class ValidSudoku {

    /**
     * Determine if a 9x9 Sudoku board is valid.
     * @param board 9x9 board with digits '1'-'9' or '.'
     * @return true if the board is valid
     */
    public static boolean isValidSudoku(char[][] board) {
        // Check rows
        for (int i = 0; i < 9; i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.' && !seen.add(board[i][j])) {
                    return false;
                }
            }
        }

        // Check columns
        for (int j = 0; j < 9; j++) {
            Set<Character> seen = new HashSet<>();
            for (int i = 0; i < 9; i++) {
                if (board[i][j] != '.' && !seen.add(board[i][j])) {
                    return false;
                }
            }
        }

        // Check 3x3 sub-boxes
        for (int box = 0; box < 9; box++) {
            Set<Character> seen = new HashSet<>();
            int rowStart = (box / 3) * 3;
            int colStart = (box % 3) * 3;
            for (int i = rowStart; i < rowStart + 3; i++) {
                for (int j = colStart; j < colStart + 3; j++) {
                    if (board[i][j] != '.' && !seen.add(board[i][j])) {
                        return false;
                    }
                }
            }
        }

        return true;
    }

    // Test method
    public static void main(String[] args) {
        char[][] board1 = {
            {'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'}
        };
        System.out.println("Test case 1 output: " + isValidSudoku(board1)); // Expected: true

        char[][] board2 = {
            {'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'}
        };
        System.out.println("Test case 2 output: " + isValidSudoku(board2)); // Expected: false
    }
}

Alternative Implementation with Encoded Keys (Single Pass)

A single pass can be done by encoding each constraint into a unique string key and storing them in one hash set. A duplicate appears when a key is seen twice.

import java.util.HashSet;
import java.util.Set;

public class ValidSudokuSinglePass {

    public static boolean isValidSudoku(char[][] board) {
        Set<String> seen = new HashSet<>();

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int boxIndex = (i / 3) * 3 + j / 3;
                    String rowKey = "row" + i + ":" + c;
                    String colKey = "col" + j + ":" + c;
                    String boxKey = "box" + boxIndex + ":" + c;

                    if (!seen.add(rowKey) || !seen.add(colKey) || !seen.add(boxKey)) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
}

Example Walkthrough

For example 1, every row, column, and 3x3 box contains only distinct digits, so the result is true.

For example 2, the top-left cell is changed from 5 to 8, making the top-left 3x3 sub-box contain two 8s. The 3 x 3 box check detects the duplicate and returns false.

Key Points

1. Rule Set: Three rules to verify - rows, columns, and 3 x 3 sub-boxes
2. Ignore Empty Cells: Cells with '.' are skipped
3. Box Indexing: For cell (i, j), the box index is (i / 3) * 3 + j / 3
4. Constant Work: Since the board size is fixed at 9 x 9, complexity is constant time
5. Single Pass Option: Encode row/column/box constraints as unique keys to validate in one pass