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.
Examples
Constraints
board.length == 9board[i].length == 9board[i][j] is a digit 1-9 or '.'.
Hash Sets for Rows, Cols, and Squares (Optimal)
Approach
Use a hash set to track the digits seen in each row, each column, and each 3x3 sub-box. We can create arrays of hash sets for rows, columns, and sub-boxes. Iterate through the board, and for each non-empty cell, check if the digit already exists in the corresponding row, column, or sub-box set. If it does, the board is invalid. Otherwise, add the digit to the sets.
Complexity Analysis
Since the board size is fixed at 9x9, iterating over it always takes 81 steps, so both time and space complexities are strictly O(1).
class Solution { public boolean isValidSudoku(char[][] board) { // Arrays of hash sets to track seen numbers Set<Character>[] rows = new HashSet[9]; Set<Character>[] cols = new HashSet[9]; Set<Character>[] boxes = new HashSet[9]; for (int i = 0; i < 9; i++) { rows[i] = new HashSet<>(); cols[i] = new HashSet<>(); boxes[i] = new HashSet<>(); } for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { char val = board[r][c]; if (val == '.') continue; // Calculate box index int boxIndex = (r / 3) * 3 + (c / 3); // If number is already seen, board is invalid if (rows[r].contains(val) || cols[c].contains(val) || boxes[boxIndex].contains(val)) { return false; } // Add number to sets rows[r].add(val); cols[c].add(val); boxes[boxIndex].add(val); } } return true; }}