Sponsored
Sponsored
This approach uses hash sets to track the unique numbers found in each row, column, and 3x3 sub-box. We iterate over each cell in the board, and check if the current value has been seen before in the current row, column, or sub-box. If it has, we return false. Otherwise, we add the value to the respective sets.
Time Complexity: O(1) because the board size is constant (9x9).
Space Complexity: O(1) due to the fixed size of additional data structures used.
1#include <stdbool.h>
2#include <string.h>
3
4bool isValidSudoku(char** board, int boardSize, int* boardColSize) {
5 bool row[9][9] = {false};
6 bool col[9][9] = {false};
7 bool box[9][9] = {false};
8
9 for (int r = 0; r < 9; r++) {
10 for (int c = 0; c < 9; c++) {
11 if (board[r][c] == '.') {
12 continue;
13 }
14 int num = board[r][c] - '1';
15 int k = (r / 3) * 3 + c / 3;
16
17 if (row[r][num] || col[c][num] || box[k][num]) {
18 return false;
19 }
20 row[r][num] = true;
21 col[c][num] = true;
22 box[k][num] = true;
23 }
24 }
25 return true;
26}This C implementation uses 2D arrays to track the presence of each digit in rows, columns, and boxes. For each digit, we check if it already exists in its respective arrays, if so, the function returns false. If not, it marks the digit as seen.
This approach seeks to replace sets with bit manipulations to compress space usage for tracking seen numbers. We increment bits in an integer representing whether a digit has been seen in rows, columns, or boxes.
Time Complexity: O(1) as the board size and iteration steps remain constant.
Space Complexity: O(1) due to the integer used for tracking positions, which is constant.
1function
This JavaScript solution capitalizes on bitwise operations similarly to other languages, thereby efficiently executing board validation through bit manipulation.