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 seen numbers. If a duplicate is found, the Sudoku is invalid.
2. Check Columns: Iterate through each column, using a HashSet to track seen numbers. If a duplicate is found, the Sudoku is invalid.
3. Check 3x3 Sub-boxes: Iterate through each 3x3 sub-box. Calculate the starting row and column indices for each sub-box. Iterate through the cells of the sub-box, using a HashSet to track seen numbers. If a duplicate is found, the Sudoku is invalid.
4. Return True: If all checks pass without finding any invalid configurations, return true.

Explanation

The solution leverages HashSets to efficiently track seen numbers in rows, columns, and 3x3 sub-boxes. HashSets provide constant-time (O(1)) average-case complexity for insertion and lookup, making the overall validation process more efficient than using nested loops with arrays or lists for duplicate detection.

The code systematically checks each row, column, and 3x3 sub-box, ensuring that all rules of a valid Sudoku are satisfied. The use of nested loops provides a structured approach to iterate through the board elements.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public bool IsValidSudoku(char[][] board) {
        // Check rows
        for (int i = 0; i < 9; i++) {
            HashSet<char> rowSet = new HashSet<char>();
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.' && !rowSet.Add(c)) return false;
            }
        }

        // Check columns
        for (int j = 0; j < 9; j++) {
            HashSet<char> colSet = new HashSet<char>();
            for (int i = 0; i < 9; i++) {
                char c = board[i][j];
                if (c != '.' && !colSet.Add(c)) return false;
            }
        }

        // Check 3x3 sub-boxes
        for (int boxRow = 0; boxRow < 3; boxRow++) {
            for (int boxCol = 0; boxCol < 3; boxCol++) {
                HashSet<char> boxSet = new HashSet<char>();
                for (int i = boxRow * 3; i < boxRow * 3 + 3; i++) {
                    for (int j = boxCol * 3; j < boxCol * 3 + 3; j++) {
                        char c = board[i][j];
                        if (c != '.' && !boxSet.Add(c)) return false;
                    }
                }
            }
        }

        return true;
    }
}

Complexity

• Time Complexity: O(n^2), where n is the size of the Sudoku board (9x9 in this case). 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 Sudoku board. This is due to the use of HashSets to store the numbers seen in each row, column, and sub-box. The space used by the HashSets is proportional to the number of cells in a row/column/sub-box (which is at most 9).