Valid Sudoku medium

Problem Statement

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 of the grid 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.

Example 1

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

Example 2

Input: board =
[["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Steps

1. Check Rows: Iterate through each row and use a set to track the numbers seen. If a number is already in the set (duplicate), the Sudoku is invalid.

2. Check Columns: Iterate through each column and use a set to track the numbers seen. Similar to rows, a duplicate indicates an invalid Sudoku.

3. Check 3x3 Sub-boxes: Iterate through each 3x3 sub-box. Calculate the starting row and column indices for each sub-box. Iterate through the cells of the sub-box and use a set to track seen numbers. Duplicates indicate an invalid Sudoku.

4. Return Result: If all checks pass without finding any invalidities, return true; otherwise, return false.

Explanation

The solution uses sets to efficiently check for duplicates. Sets only allow unique elements, so adding an element that already exists will not change the set's size. We can check for duplicates by comparing the set's size to the number of elements added. If they differ, a duplicate exists. This approach ensures that each row, column, and 3x3 sub-box contains only unique digits from 1 to 9.

Code

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

bool isValidSudoku(vector<vector<char>>& board) {
    // Check rows
    for (int i = 0; i < 9; ++i) {
        unordered_set<char> rowSet;
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] != '.') {
                if (rowSet.count(board[i][j])) return false;
                rowSet.insert(board[i][j]);
            }
        }
    }

    // Check columns
    for (int j = 0; j < 9; ++j) {
        unordered_set<char> colSet;
        for (int i = 0; i < 9; ++i) {
            if (board[i][j] != '.') {
                if (colSet.count(board[i][j])) return false;
                colSet.insert(board[i][j]);
            }
        }
    }

    // Check 3x3 sub-boxes
    for (int boxRow = 0; boxRow < 3; ++boxRow) {
        for (int boxCol = 0; boxCol < 3; ++boxCol) {
            unordered_set<char> boxSet;
            for (int i = boxRow * 3; i < (boxRow + 1) * 3; ++i) {
                for (int j = boxCol * 3; j < (boxCol + 1) * 3; ++j) {
                    if (board[i][j] != '.') {
                        if (boxSet.count(board[i][j])) return false;
                        boxSet.insert(board[i][j]);
                    }
                }
            }
        }
    }

    return true;
}

int main() {
  //Example usage (You can replace this with other test cases)
  vector<vector<char>> board = {
    {'5','3','.','.','7','.','.','.','.'},
    {'6','.','.','1','9','5','.','.','.'},
    {'.','9','8','.','.','.','.','6','.'},
    {'8','.','.','.','6','.','.','.','3'},
    {'4','.','.','8','.','3','.','.','1'},
    {'7','.','.','.','2','.','.','.','6'},
    {'.','6','.','.','.','.','2','8','.'},
    {'.','.','.','4','1','9','.','.','5'},
    {'.','.','.','.','8','.','.','7','9'}
  };

  if (isValidSudoku(board)) {
    cout << "Sudoku is valid" << endl;
  } else {
    cout << "Sudoku is invalid" << endl;
  }
  return 0;
}

Complexity

• Time Complexity: O(n), where n is the number of cells in the Sudoku board (81). We iterate through the rows, columns, and sub-boxes once. The set operations (insertion and lookup) have an average time complexity of O(1).

• Space Complexity: O(n), because we use sets to store the numbers seen in each row, column, and sub-box. In the worst case, each set could contain up to 9 elements.