36. Valid Sudoku

Intuition

The problem requires us to check if a given partially filled 9x9 Sudoku board is valid. The key point is that we only need to validate the filled cells according to the Sudoku 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 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

By keeping track of the numbers seen so far in each row, column, and 3x3 sub-box, we can efficiently validate the board as we iterate through each cell.

Approach

1. Initialization: - Use three lists of dictionaries to track the numbers seen in each row, column, and 3x3 sub-box. Each list has 9 dictionaries, one for each row, column, and sub-box.
2. Iterate through the board: - Loop through each cell in the 9x9 grid using nested loops for rows and columns. - For each cell that contains a number (not '.'), do the following: - Calculate the index of the corresponding 3x3 sub-box. - Check if the number already exists in the current row, column, or sub-box using the respective dictionaries. - If the number is already present in any of the dictionaries, the board is not valid, so return false. - If the number is not present, mark it as seen in the respective dictionaries for the current row, column, and sub-box.
3. Return the result: - If the entire board is processed without finding any conflicts, return true, indicating the Sudoku board is valid.

Complexity

Time Complexity:

O(1)

• The board size is fixed at 9x9, so the operations are bounded and do not scale with input size.

Space Complexity:

O(1)

• We use a fixed amount of extra space for the dictionaries, which do not grow with input size. Each dictionary can contain at most 9 entries, corresponding to the digits 1-9.

Code

C++

class Solution {
public:
    bool isValidSudoku(vector>& board) {
        vector> rows(9);
        vector> cols(9);
        vector> boxes(9);
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                if (board[r][c] != '.') {
                    char num = board[r][c];
                    int boxIndex = (r / 3) * 3 + (c / 3);
                    if (rows[r][num] || cols[c][num] || boxes[boxIndex][num]) {
                        return false;}
                    rows[r][num] = true;
                    cols[c][num] = true;
                    boxes[boxIndex][num] = true;
                }
            }
        }
        return true;
    }
};

Python

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [{} for _ in range(9)]
        cols = [{} for _ in range(9)]
        boxes = [{} for _ in range(9)]
        for r in range(9):
            for c in range(9):
                if board[r][c] != '.':
                    num = board[r][c]
                    box_index = (r // 3) * 3 + (c // 3)
                    if num in rows[r] or num in cols[c] or num in boxes[box_index]:
                        return False
                    rows[r][num] = True
                    cols[c][num] = True
                    boxes[box_index][num] = True
        return True

Java

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashMap[] rows = new HashMap[9];
        HashMap[] cols = new HashMap[9];
        HashMap[] boxes = new HashMap[9];
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashMap<>();
            cols[i] = new HashMap<>();
            boxes[i] = new HashMap<>();}
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] != '.') {
                    char num = board[r][c];
                    int boxIndex = (r / 3) * 3 + (c / 3);
                    if (rows[r].getOrDefault(num, false) || cols[c].getOrDefault(num, false) || boxes[boxIndex].getOrDefault(num, false)) {
                        return false;}
                    rows[r].put(num, true);
                    cols[c].put(num, true);
                    boxes[boxIndex].put(num, true);
                }
            }
        }
        return true;
    }}

JavaScript

var isValidSudoku = function(board) {
    let rows = new Array(9).fill(0).map(() => ({}))
    let cols = new Array(9).fill(0).map(() => ({}))
    let box = new Array(9).fill(0).map(() => ({}))
    for(let r = 0; r < 9; r++){
        for(let c = 0; c < 9; c++){
            if(board[r][c] !== "."){
                let num = board[r][c]
                let boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3)
                if(rows[r][num] || cols[c][num] || box[boxIndex][num]){
                    return false}
                rows[r][num]  = true
                cols[c][num]  = true
                box[boxIndex][num] = true
            }
        }}
    return true
};