Valid Sudoku

Problem

You are given a 9 x 9 Sudoku board board. A Sudoku board is valid if the following rules are followed:

1. Each row must contain the digits 1-9 without duplicates.
2. Each column must contain the digits 1-9 without duplicates.
3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without duplicates.

Return true if the Sudoku board is valid, otherwise return false

Note: A board does not need to be full or be solvable to be valid.

Examples

Example 1:

Input: board =
[["1","2",".",".","3",".",".",".","."],
 ["4",".",".","5",".",".",".",".","."],
 [".","9","8",".",".",".",".",".","3"],
 ["5",".",".",".","6",".",".",".","4"],
 [".",".",".","8",".","3",".",".","5"],
 ["7",".",".",".","2",".",".",".","6"],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".","4","1","9",".",".","8"],
 [".",".",".",".","8",".",".","7","9"]]

Output: true

Example 2:

Input: board =
[["1","2",".",".","3",".",".",".","."],
 ["4",".",".","5",".",".",".",".","."],
 [".","9","1",".",".",".",".",".","3"],
 ["5",".",".",".","6",".",".",".","4"],
 [".",".",".","8",".","3",".",".","5"],
 ["7",".",".",".","2",".",".",".","6"],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".","4","1","9",".",".","8"],
 [".",".",".",".","8",".",".","7","9"]]

Output: false

Explanation: There are two 1’s in the top-left 3x3 sub-box.

Constraints

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.

You should aim for a solution as good or better than O(n^2) time and O(n^2) space, where n is the number of rows in the square grid.

Solution

Scan linearly, inserting numbers we see. We check the row/col/square if we’ve seen this number before.

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        std::array<std::unordered_set<char>, 9> row_nums;
        std::array<std::unordered_set<char>, 9> col_nums;
        std::array<std::unordered_set<char>, 9> sqr_nums;
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                char num = board[r][c];
                if (num == '.') { continue; }
                int s = (r/3) * 3 + (c/3);
                if (row_nums[r].contains(num)) { return false; }
                if (col_nums[c].contains(num)) { return false; }
                if (sqr_nums[s].contains(num)) { return false; }
                row_nums[r].insert(num);
                col_nums[c].insert(num);
                sqr_nums[s].insert(num);
            }
        }
        return true;
    }
};