# Valid Sudoku
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/valid-sudoku)
Canonical: https://scaleengineer.com/dsa/problems/valid-sudoku
**Data structures:** Array, Hash Table, Matrix
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [DoorDash](https://scaleengineer.com/companies/doordash), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Karat](https://scaleengineer.com/companies/karat), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [Veeva Systems](https://scaleengineer.com/companies/veeva-systems), [Autodesk](https://scaleengineer.com/companies/autodesk), [Snap](https://scaleengineer.com/companies/snap), [Media.net](https://scaleengineer.com/companies/media.net), [Confluent](https://scaleengineer.com/companies/confluent), [Geico](https://scaleengineer.com/companies/geico), [MongoDB](https://scaleengineer.com/companies/mongodb), [Attentive](https://scaleengineer.com/companies/attentive), [Instacart](https://scaleengineer.com/companies/instacart), [Riot Games](https://scaleengineer.com/companies/riot-games), [Samsara](https://scaleengineer.com/companies/samsara), [Waymo](https://scaleengineer.com/companies/waymo)
---
## Problem
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 according to the mentioned rules.

**Example 1:**

![](https://assets.glich.co/dsa/valid-sudoku/image0.png) 

**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.

**Constraints:**

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

# Approaches
## Brute Force Validation
This approach iterates through every cell of the Sudoku board. For each cell that contains a number, it performs three separate checks: one for the row, one for the column, and one for the 3x3 sub-box to ensure there are no other occurrences of the same number.
**Time:** O(N^3) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Uses constant extra space, O(1).
**Cons:** Highly inefficient due to a large number of redundant comparisons.; The time complexity is cubic with respect to the board size (N), making it unsuitable for larger boards.
### Explanation
The algorithm uses nested loops to traverse each cell `(i, j)` of the 9x9 board. If `board[i][j]` contains a digit, it's stored. Then, three validation checks are performed for this digit. If any of these checks find a duplicate, the board is invalid, and the function returns `false`. If the loops complete without finding any duplicates for any cell, the board is valid, and the function returns `true`. This method is straightforward but highly inefficient due to redundant comparisons. For example, the relationship between `board[0][1]` and `board[0][2]` will be checked when processing `(0,1)` and again when processing `(0,2)`. 

```java
class Solution {
    public boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    if (!isValidPlacement(board, i, j)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    private boolean isValidPlacement(char[][] board, int row, int col) {
        char val = board[row][col];

        // Check row for duplicates
        for (int k = 0; k < 9; k++) {
            if (k != col && board[row][k] == val) {
                return false;
            }
        }

        // Check column for duplicates
        for (int k = 0; k < 9; k++) {
            if (k != row && board[k][col] == val) {
                return false;
            }
        }

        // Check 3x3 sub-box for duplicates
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int r = startRow; r < startRow + 3; r++) {
            for (int c = startCol; c < startCol + 3; c++) {
                if (r != row || c != col) { // Corrected condition
                    if (board[r][c] == val) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
}
```
### Algorithm
- Iterate through each cell `(i, j)` of the 9x9 board.
- If the cell `board[i][j]` contains a digit, store its value.
- For the current cell's value, perform three separate validation checks:
  1. **Row Check:** Scan all other cells in the same row `i` to see if the digit appears again. If a duplicate is found, return `false`.
  2. **Column Check:** Scan all other cells in the same column `j` for the same digit. If a duplicate is found, return `false`.
  3. **Sub-box Check:** Identify the 3x3 sub-box for cell `(i, j)`. Scan all other cells in this sub-box for the same digit. If a duplicate is found, return `false`.
- If the loops complete without finding any duplicates for any cell, the board is valid. Return `true`.

## Grouped Validation (Rows, Columns, and Boxes)
This approach improves upon the brute-force method by validating all rows, then all columns, and finally all 3x3 sub-boxes in separate phases. This avoids the redundant checks of the previous method.
**Time:** O(N^2) · **Space:** O(N)
**Pros:** Much more efficient than brute force with O(N^2) time complexity.; Code is well-structured and easy to follow.; Space efficient, using O(N) extra space.
**Cons:** Iterates over the board three times, which can be slightly less performant than a single-pass approach due to loop overhead and potentially worse cache performance.
### Explanation
The validation is split into three distinct parts:
1.  **Row Validation:** Iterate through each of the 9 rows. For each row, use a `HashSet` (or a boolean array) to keep track of the digits encountered. If a digit is seen more than once in the same row, the board is invalid.
2.  **Column Validation:** Similarly, iterate through each of the 9 columns. Use a fresh `HashSet` for each column to check for duplicate digits.
3.  **Sub-box Validation:** Iterate through each of the 9 3x3 sub-boxes. A `HashSet` is used for each sub-box to ensure no digit is repeated within it. The sub-boxes can be traversed by iterating their top-left corners, e.g., `(0,0), (0,3), (0,6), ...`.
If all three validation phases complete successfully, the board is valid. This method processes each cell three times in total.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // Check rows
        for (int i = 0; i < 9; i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                char current = board[i][j];
                if (current != '.') {
                    if (seen.contains(current)) {
                        return false;
                    }
                    seen.add(current);
                }
            }
        }

        // Check columns
        for (int j = 0; j < 9; j++) {
            Set<Character> seen = new HashSet<>();
            for (int i = 0; i < 9; i++) {
                char current = board[i][j];
                if (current != '.') {
                    if (seen.contains(current)) {
                        return false;
                    }
                    seen.add(current);
                }
            }
        }

        // Check 3x3 sub-boxes
        for (int boxRow = 0; boxRow < 3; boxRow++) {
            for (int boxCol = 0; boxCol < 3; boxCol++) {
                Set<Character> seen = new HashSet<>();
                int startRow = boxRow * 3;
                int startCol = boxCol * 3;
                for (int i = startRow; i < startRow + 3; i++) {
                    for (int j = startCol; j < startCol + 3; j++) {
                        char current = board[i][j];
                        if (current != '.') {
                            if (seen.contains(current)) {
                                return false;
                            }
                            seen.add(current);
                        }
                    }
                }
            }
        }

        return true;
    }
}
```
### Algorithm
- **Validate Rows:**
  - For each row `i` from 0 to 8:
    - Use a `HashSet` to track seen digits.
    - Iterate through the row. If a digit is already in the set, return `false`. Otherwise, add it.
- **Validate Columns:**
  - For each column `j` from 0 to 8:
    - Use a new `HashSet`.
    - Iterate through the column. If a digit is already in the set, return `false`. Otherwise, add it.
- **Validate Sub-boxes:**
  - For each of the 9 sub-boxes:
    - Use a new `HashSet`.
    - Iterate through the 3x3 cells of the box. If a digit is already in the set, return `false`. Otherwise, add it.
- If all checks pass, return `true`.

## Single Pass with Hash Sets
This is the most efficient approach. It validates the board by iterating through each cell only once. It uses auxiliary data structures (arrays of `HashSet`s) to keep track of the numbers seen in each row, column, and 3x3 sub-box simultaneously.
**Time:** O(N^2) · **Space:** O(N^2)
**Pros:** Most time-efficient as it traverses the board only once.; Elegant solution that combines all checks in a single loop.
**Cons:** Uses more space, O(N^2), compared to the grouped validation approach.
### Explanation
We declare three arrays of `HashSet`s: `rows[9]`, `cols[9]`, and `boxes[9]`. The algorithm iterates through the board cell by cell from `(0,0)` to `(8,8)`. For each cell `(i, j)` containing a digit `d`, it calculates the index of its sub-box using the formula `box_index = (i / 3) * 3 + (j / 3)`. It then checks if `d` is already present in the corresponding sets for its row, column, and box. If a duplicate is found in any of them, the board is invalid. Otherwise, the digit is added to all three sets to be checked against subsequent cells. If the entire board is traversed without finding any duplicates, the function returns `true`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<Character>[] rows = new HashSet[9];
        Set<Character>[] cols = new HashSet[9];
        Set<Character>[] boxes = new HashSet[9];
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            boxes[i] = new HashSet<>();
        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char val = board[i][j];
                if (val == '.') {
                    continue;
                }

                // Check row
                if (rows[i].contains(val)) {
                    return false;
                }
                rows[i].add(val);

                // Check column
                if (cols[j].contains(val)) {
                    return false;
                }
                cols[j].add(val);

                // Check 3x3 box
                int boxIndex = (i / 3) * 3 + (j / 3);
                if (boxes[boxIndex].contains(val)) {
                    return false;
                }
                boxes[boxIndex].add(val);
            }
        }
        return true;
    }
}
```
### Algorithm
- Initialize three arrays of `HashSet`s: `rows`, `cols`, and `boxes`, each of size 9.
- Iterate through the board from cell `(i, j) = (0,0)` to `(8,8)`.
- For each cell that contains a digit `d`:
  - Calculate the sub-box index: `box_index = (i / 3) * 3 + (j / 3)`.
  - Check if `d` is already present in `rows[i]`. If so, return `false`.
  - Check if `d` is already present in `cols[j]`. If so, return `false`.
  - Check if `d` is already present in `boxes[box_index]`. If so, return `false`.
  - If no duplicates are found, add `d` to all three sets: `rows[i]`, `cols[j]`, and `boxes[box_index]`.
- If the entire board is traversed without returning, the board is valid. Return `true`.

# Solutions
### Java

```java
class Solution { public boolean isValidSudoku ( char [][] board ) { boolean [][] row = new boolean [ 9 ][ 9 ]; boolean [][] col = new boolean [ 9 ][ 9 ]; boolean [][] sub = new boolean [ 9 ][ 9 ]; for ( int i = 0 ; i < 9 ; ++ i ) { for ( int j = 0 ; j < 9 ; ++ j ) { char c = board [ i ][ j ]; if ( c == '.' ) { continue ; } int num = c - '0' - 1 ; int k = i / 3 * 3 + j / 3 ; if ( row [ i ][ num ] || col [ j ][ num ] || sub [ k ][ num ]) { return false ; } row [ i ][ num ] = true ; col [ j ][ num ] = true ; sub [ k ][ num ] = true ; } } return true ; } }
```

### JavaScript

```javascript
/** * @param {character[][]} board * @return {boolean} */ var isValidSudoku =
  function (board) {
    const row = [...Array(9)].map(() => Array(9).fill(false));
    const col = [...Array(9)].map(() => Array(9).fill(false));
    const sub = [...Array(9)].map(() => Array(9).fill(false));
    for (let i = 0; i < 9; ++i) {
      for (let j = 0; j < 9; ++j) {
        const num = board[i][j].charCodeAt() - " 1 ".charCodeAt();
        if (num < 0 || num > 8) {
          continue;
        }
        const k = Math.floor(i / 3) * 3 + Math.floor(j / 3);
        if (row[i][num] || col[j][num] || sub[k][num]) {
          return false;
        }
        row[i][num] = true;
        col[j][num] = true;
        sub[k][num] = true;
      }
    }
    return true;
  };

```

### Python

```python
class Solution : def isValidSudoku ( self , board : List [ List [ str ]]) -> bool : row = [[ False ] * 9 for _ in range ( 9 )] col = [[ False ] * 9 for _ in range ( 9 )] sub = [[ False ] * 9 for _ in range ( 9 )] for i in range ( 9 ): for j in range ( 9 ): c = board [ i ][ j ] if c == '.' : continue num = int ( c ) - 1 k = i // 3 * 3 + j // 3 if row [ i ][ num ] or col [ j ][ num ] or sub [ k ][ num ]: return False row [ i ][ num ] = True col [ j ][ num ] = True sub [ k ][ num ] = True return True
```

### CPP

```cpp
class Solution { public: bool isValidSudoku ( vector < vector < char >>& board ) { vector < vector < bool >> row ( 9 , vector < bool > ( 9 , false )); vector < vector < bool >> col ( 9 , vector < bool > ( 9 , false )); vector < vector < bool >> sub ( 9 , vector < bool > ( 9 , false )); for ( int i = 0 ; i < 9 ; ++ i ) { for ( int j = 0 ; j < 9 ; ++ j ) { char c = board [ i ][ j ]; if ( c == '.' ) continue ; int num = c - '0' - 1 ; int k = i / 3 * 3 + j / 3 ; if ( row [ i ][ num ] || col [ j ][ num ] || sub [ k ][ num ]) { return false ; } row [ i ][ num ] = true ; col [ j ][ num ] = true ; sub [ k ][ num ] = true ; } } return true ; } };
```