---
id: 36
title: Valid Sudoku
difficulty: Medium
tags:
  - array
  - hash-table
  - matrix
status: Solved
date_solved: 2026-06-05
leetcode_url: https://leetcode.com/problems/valid-sudoku/
review_needed: false
---

# 36. Valid Sudoku

> [!info] **Problem Link**: [LeetCode - Valid Sudoku](https://leetcode.com/problems/valid-sudoku/)

## 📝 Problem Description

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
**Input:**
```python
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:**
```python
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.

---

## 💡 Approaches & Explanations

### Approach 1: Hash Sets for Rows, Columns, and Boxes — *Optimal*
We use three collections of sets to track the numbers we've seen:
1. `rows`: 9 sets, one for each row.
2. `cols`: 9 sets, one for each column.
3. `boxes`: 9 sets, one for each 3x3 sub-grid.

We iterate through every cell `(r, c)` in the 9x9 board. If the cell is not empty (i.e., not `.`):
- Calculate the box index: `box_idx = (r // 3) * 3 + (c // 3)`.
- Check if the digit already exists in `rows[r]`, `cols[c]`, or `boxes[box_idx]`.
- If it exists, the board is invalid.
- If not, add the digit to all three sets and continue.

#### 📊 Complexity Analysis
- **Time Complexity:** $\mathcal{O}(1)$ or $\mathcal{O}(N^2)$ where $N=9$. Since the board size is fixed at 9x9, we always perform 81 operations.
- **Space Complexity:** $\mathcal{O}(1)$ or $\mathcal{O}(N^2)$ to store the sets for rows, columns, and boxes. In the worst case, we store 81 entries.

---

## 💻 Code Implementations

### Python3
```python
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        squares = collections.defaultdict(set)  # key = (r // 3, c // 3)

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                if (
                    board[r][c] in rows[r]
                    or board[r][c] in cols[c]
                    or board[r][c] in squares[(r // 3, c // 3)]
                ):
                    return False
                cols[c].add(board[r][c])
                rows[r].add(board[r][c])
                squares[(r // 3, c // 3)].add(board[r][c])

        return True
```

---

## 🧠 Key Takeaways & Lessons
- **Coordinate Mapping:** Mapping a 2D coordinate `(r, c)` to a 1D sub-grid index or a tuple key `(r // 3, c // 3)` is a crucial technique for matrix problems.
- **Trade-off:** Using hash sets provides $\mathcal{O}(1)$ lookup time, making the validation process very efficient.
- **Constraints Matter:** Since the board size is fixed (9x9), "optimal" here refers to the single-pass nature and clean logic rather than asymptotic growth beyond the constant size.