Valid Sudoku
LeetCode #36 · Medium · Arrays · C++ solution with worked-out approach and complexity analysis.
Approach
Validate rows, columns, and 3x3 sub-boxes
1. Create a transposed board to easily check columns 2. Check each row and column for duplicates 3. Check each 3x3 sub-box for duplicates
Time
O(1)
board is always 9x9
Space
O(1)
fixed size arrays
Problem description(from LeetCode)
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 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 according to the mentioned rules.
Examples
Example 1
- Input:
- board =
- Output:
- true
Constraints
- •board.length == 9
- •board[i].length == 9
- •board[i][j] is a digit 1-9 or '.'.
C++ Solution
solution.cpp
class Solution {
public:
bool isValidSudoku(vector<vector<char>> &board) {
vector<vector<char>> boardT(9, vector<char>(9, 'a'));
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[i].size(); j++) {
boardT[j][i] = board[i][j];
if (i % 3 == 0 && j % 3 == 0) {
if (!isValidSubBox(board, i, j)) {
return false;
}
}
}
}
for (int i = 0; i < board.size(); i++) {
if (!isValidSequence(board[i])) {
return false;
}
if (!isValidSequence(boardT[i])) {
return false;
}
}
return true;
}
bool isValidSequence(vector<char> &sequence) {
bool numbers[9] = {0};
for (int i = 0; i < sequence.size(); i++) {
if (sequence[i] != '.') {
if (numbers[sequence[i] - '1']) {
return false;
}
numbers[sequence[i] - '1'] = 1;
}
}
return true;
}
bool isValidSubBox(vector<vector<char>> &board, int row, int column) {
bool numbers[9] = {0};
for (int i = row; i < row + 3; i++) {
for (int j = column; j < column + 3; j++) {
if (board[i][j] != '.') {
if (numbers[(board[i][j] - '1')]) {
return false;
}
numbers[board[i][j] - '1'] = 1;
}
}
}
return true;
}
};