Valid Sudoku 🧠

LeetCode Link: Valid Sudoku

Difficulty: Medium

Problem Explanation 📝

Problem: LeetCode 36 - Valid Sudoku

Description: Given a 9 x 9 Sudoku board, determine if it is a valid Sudoku. The board is only partially filled, and each digit from 1 to 9 must appear exactly once in each row, column, and 3 x 3 sub-grid.

Intuition: To check if a Sudoku board is valid, we need to verify that each digit appears exactly once in each row, column, and 3 x 3 sub-grid. We can use three separate 2D arrays to keep track of the digits already used in each row, column, and sub-grid.

Approach:

1. Initialize three 2D arrays, usedRows, usedCols, and usedSubgrids, with all values set to 0.
2. Iterate through each cell in the Sudoku board:

• If the current cell is not empty:
• Convert the character to an integer and subtract 1 to get the corresponding number index.
• Calculate the sub-grid index based on the current cell's position.
• Check if the number is already used in the current row, column, or sub-grid by looking at the corresponding index in the usedRows, usedCols, and usedSubgrids arrays.
• If the number is already used, return false as the Sudoku board is not valid.
• Mark the number as used in the current row, column, and sub-grid by setting the corresponding index to 1 in the usedRows, usedCols, and usedSubgrids arrays.

3. If all cells pass the checks, return true as the Sudoku board is valid.

⌛ Time Complexity: The time complexity of this approach is O(1) since the Sudoku board has a fixed size of 9 x 9, and the iteration is constant.

💾 Space Complexity: The space complexity is O(1) since the arrays used for tracking the used digits (usedRows, usedCols, and usedSubgrids) have a fixed size of 9 x 9.

Solutions 💡

Cpp 💻

class Solution {
  public:
    bool isValidSudoku(vector<vector<char>> &board) {
        int usedRows[9][9] = {0};
        int usedCols[9][9] = {0};
        int usedSubgrids[9][9] = {0};

        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0' - 1;
                    int subgridIndex = (i / 3) * 3 + j / 3;

                    if (usedRows[i][num] || usedCols[j][num] || usedSubgrids[subgridIndex][num]) {
                        return false;
                    }

                    usedRows[i][num] = usedCols[j][num] = usedSubgrids[subgridIndex][num] = 1;
                }
            }
        }

        return true;
    }
};

Python 🐍

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        seen = set()

        for i in range(9):
            for j in range(9):
                if board[i][j] != ".":
                    num = board[i][j]
                    if (
                        (i, num) in seen
                        or (num, j) in seen
                        or (i // 3, j // 3, num) in seen
                    ):
                        return False
                    seen.add((i, num))
                    seen.add((num, j))
                    seen.add((i // 3, j // 3, num))

        return True