Valid Sudoku medium

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:

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.

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.

Steps

1. Check Rows: Iterate through each row, using a HashSet to track the numbers encountered. If a duplicate is found, the Sudoku is invalid.
2. Check Columns: Iterate through each column, similarly using a HashSet to track numbers. If a duplicate is found, the Sudoku is invalid.
3. Check 3x3 Sub-boxes: Iterate through each 3x3 sub-box. Calculate the starting indices for each sub-box (rowStart, colStart). Iterate through the sub-box, using a HashSet to track numbers. If a duplicate is found, the Sudoku is invalid.

Explanation

The solution leverages the properties of HashSet in Java. A HashSet only allows unique elements. By adding each number in a row, column, or 3x3 sub-box to a HashSet, we can efficiently detect duplicates. If a duplicate is added, it means the Sudoku rule is violated. The code systematically checks all rows, columns, and sub-boxes. If any violation is found, false is returned immediately. If all checks pass, it means the Sudoku board is valid, and true is returned.

Code

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

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // Check rows
        for (int i = 0; i < 9; i++) {
            if (!isValidUnit(board, i, 0, i, 8)) return false; 
        }

        // Check columns
        for (int j = 0; j < 9; j++) {
            if (!isValidUnit(board, 0, j, 8, j)) return false;
        }

        // Check 3x3 sub-boxes
        for (int i = 0; i < 9; i += 3) {
            for (int j = 0; j < 9; j += 3) {
                if (!isValidUnit(board, i, j, i + 2, j + 2)) return false;
            }
        }

        return true;
    }

    private boolean isValidUnit(char[][] board, int rowStart, int colStart, int rowEnd, int colEnd) {
        Set<Character> seen = new HashSet<>();
        for (int i = rowStart; i <= rowEnd; i++) {
            for (int j = colStart; j <= colEnd; j++) {
                char num = board[i][j];
                if (num != '.') {
                    if (!seen.add(num)) return false; // Duplicate found
                }
            }
        }
        return true;
    }
}

Complexity

• Time Complexity: O(n^2), where n is the size of the board (9x9). We iterate through each cell of the board three times (rows, columns, and sub-boxes).
• Space Complexity: O(n), where n is the size of the board. The space used by the HashSet is proportional to the number of filled cells in a row, column, or sub-box (at most 9).