Valid Sudoku

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

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

Approach: Single Hash Set with String Encoding

Instead of maintaining 27 different sets (9 for rows, 9 for columns, 9 for boxes), we can use a single Hash Set to track all constraints simultaneously. We do this by encoding the location and the value into a unique string format.

For example, if we see the number 5 at row 0 and column 2, we generate three unique strings:

• 'r05' (indicates 5 is in row 0)
• 'c25' (indicates 5 is in column 2)
• 'b05' (indicates 5 is in box 0)

The main trick is determining which $3 \times 3$ sub-box a specific cell (i, j) belongs to. We can uniquely identify the 9 sub-boxes (indexed 0 to 8) using the formula:
boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3)

1. Initialize a single Hash Set called set.
2. Iterate through every cell in the $9 \times 9$ grid.
3. If the cell is empty ("."), skip it.
4. For a filled cell, compute its boxIndex and generate the three encoded strings for its row, column, and box.
5. Check if any of these strings already exist in the set.
   • If they do, we found a duplicate! Return false.
   • If they don’t, add all three strings to the set.
6. If the loop finishes without violations, return true.

Solution

/**
 * @param {character[][]} board
 * @return {boolean}
 */
function isValidSudoku (board) {
    const set = new Set();
    
	for (let i = 0; i < board.length; i++) {
		for (let j = 0; j < board[i].length; j++) {
			const val = board[i][j];
            
			if (val !== '.') {
				const rowIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
                
				if (set.has('r' + i + val) || set.has('c' + j + val) || set.has('b' + rowIndex + val)) {
					return false;
                } else {
					set.add('r' + i + val);
					set.add('c' + j + val);
					set.add('b' + rowIndex + val);
				}
			}
		}
	}
    
	return true;
};

Complexity Analysis

• Time Complexity: $O(1)$ (or strictly $O(9^2)$). We perform exactly 81 iterations since the board is fixed at $9 \times 9$. Set lookups and insertions take constant time $O(1)$.
• Space Complexity: $O(1)$. The Hash Set stores at most $81 \times 3 = 243$ strings. Since this is bounded by a constant, the space requirement is constant.