36. Valid Sudoku
1. Description
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 of the grid must contain the digits 1-9 without repetition.
2. Note
- A Sudoku board (partially filled) could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.
3. Example
Example 1:
Output: true
4. Constraints
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit or ‘.’.
5. Solutions
My Accepted Solution
Time complexity: O(1), or nodes in i_board
Space complexity: O(1), or nodes in i_board
class Solution {
public:
bool isValidSudoku(const vector<vector<char>> &board) {
unordered_map<pair<int, char>, int, pair_hash> row_letter_count, column_letter_count,
box_letter_count;
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[0].size(); ++j) {
char letter = board[i][j];
if (letter != '.' &&
(++row_letter_count[{i, letter}] > 1 ||
++column_letter_count[{j, letter}] > 1 ||
++box_letter_count[{i / 3 * 3 + j / 3, letter}] > 1)) {
return false;
}
}
}
return true;
}
private:
struct pair_hash {
std::size_t operator()(const pair<int, char> &k) const {
string hash_input = to_string(k.first) + string("_") + string(1, k.second);
return std::hash<std::string>{}(hash_input);
}
};
};