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.
1def isValidSudoku(board):
2 from collections import defaultdict
3 rows = defaultdict(set)
4 columns = defaultdict(set)
5 boxes = defaultdict(set)
6 for r in range(9):
7 for c in range(9):
8 if board[r][c] == '.':
9 continue
10 if (board[r][c] in rows[r] or
11 board[r][c] in columns[c] or
12 board[r][c] in boxes[(r // 3, c // 3)]):
13 return False
14 rows[r].add(board[r][c])
15 columns[c].add(board[r][c])
16 boxes[(r // 3, c // 3)].add(board[r][c])
17 return TrueThis solution uses three dictionaries, each containing sets, to keep track of seen values in rows, columns, and boxes. The key for the boxes dictionary is a tuple representing the box index. As we iterate, we skip any empty cells and check if the number already exists in any of its corresponding set. If it does, the Sudoku is invalid. Otherwise, we add the number to the corresponding sets and continue.
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.
1#include <vector>
2using namespace std;
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int rows[9] = {0}, cols[9] = {0}, boxes[9] = {0};
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] == '.') continue;
int bit = 1 << (board[r][c] - '1');
int boxIndex = (r / 3) * 3 + c / 3;
if ((rows[r] & bit) || (cols[c] & bit) || (boxes[boxIndex] & bit))
return false;
rows[r] |= bit;
cols[c] |= bit;
boxes[boxIndex] |= bit;
}
}
return true;
}
};This C++ bit manipulation approach employs the same methodology as other languages, using integer arithmetic and bit shifts for rapid checks and updates.