valid Soduko

36.Valid Sudoku

Array

Hash Table

Matrix

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: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the nine 3 x 3 sub-boxes must contain the digits 1-9 without repetition.

Example:

Input:

board = [
  ["5","3",".",".","7",".",".",".","."]],
  ["6",".",".",".","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

The board is valid as no digit appears twice in any row, column, or 3x3 sub-box.

Algorithm:

1. Single pass through board checking three conditions simultaneously:
2. Use HashSets to track digits in each row
3. Use HashSets to track digits in each column
4. Use HashSets to track digits in each 3x3 sub-box
5. For sub-boxes, use r = 3*(i/3) and c = 3*(i%3) to map positions

Complexity:

Time: O(1) | Space: O(1)

Constant because board size is fixed 9x9

Java Solution:

public boolean isValidSudoku(char[][] board) {
    
    for (int i = 0; i < 9; i++) {
        Set<Character> horizontal = new HashSet<>();
        Set<Character> vertical = new HashSet<>();
        Set<Character> square = new HashSet<>();
        
        // For Squares
        int r = 3 * (i/3);
        int c = 3 * (i%3);
        
        for (int j = 0; j < 9; j++) {
            // Check horizontal
            if (board[i][j] != '.' && !horizontal.add(board[i][j])) 
                return false;
            
            // Check vertical
            if (board[j][i] != '.' && !vertical.add(board[j][i])) 
                return false;
            
            // Check 3x3 square
            if (board[r + j/3][c + j%3] != '.' && 
                !square.add(board[r + j/3][c + j%3])) 
                return false;
        }  
    }
    
    return true;
}

Python Solution:

def isValidSudoku(self, board: List[List[str]]) -> bool:
    for i in range(9):
        horizontal = set()
        vertical = set()
        square = set()
        
        # Calculate top-left corner of current 3x3 square
        r = 3 * (i // 3)
        c = 3 * (i % 3)
        
        for j in range(9):
            # Check horizontal
            if board[i][j] != '.':
                if board[i][j] in horizontal:
                    return False
                horizontal.add(board[i][j])
            
            # Check vertical
            if board[j][i] != '.':
                if board[j][i] in vertical:
                    return False
                vertical.add(board[j][i])
            
            # Check square
            curr = board[r + j//3][c + j%3]
            if curr != '.':
                if curr in square:
                    return False
                square.add(curr)
    
    return True

C++ Solution:

bool isValidSudoku(vector<vector<char>>& board) {
    for (int i = 0; i < 9; i++) {
        unordered_set<char> horizontal;
        unordered_set<char> vertical;
        unordered_set<char> square;
        
        // For Squares
        int r = 3 * (i/3);
        int c = 3 * (i%3);
        
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.' && 
                !horizontal.insert(board[i][j]).second)
                return false;
            
            if (board[j][i] != '.' && 
                !vertical.insert(board[j][i]).second)
                return false;
            
            char curr = board[r + j/3][c + j%3];
            if (curr != '.' && 
                !square.insert(curr).second)
                return false;
        }
    }
    
    return true;
}