# NEETCODE - Arrays and Hashing: Valid Sudoku

## Problem Statement

You are given a 9x9 Sudoku board. Determine if the board is valid according to these rules:

1. Each row must contain the digits 1-9 without duplicates
2. Each column must contain the digits 1-9 without duplicates
3. Each of the nine 3x3 sub-boxes must contain the digits 1-9 without duplicates

**Important:** A board does not need to be full or solvable to be valid. Empty cells are represented by ".".

**Example:**

```python
board = [
    ["1","2",".",".","3",".",".",".","."],
    ["4",".",".","5",".",".",".",".","."],
    [".","9","8",".",".",".",".",".","3"],
    ["5",".",".",".","6",".",".",".","4"],
    [".",".",".","8",".","3",".",".","5"],
    ["7",".",".",".","2",".",".",".","6"],
    [".",".",".",".",".",".","2",".","."],
    [".",".",".","4","1","9",".",".","8"],
    [".",".",".",".","8",".",".","7","9"]
]

Output: True
```

**Constraints:**
- Board is always 9x9
- Board cells contain digits 1-9 or "."
- Must validate all three rules simultaneously

## Solutions Progression

### Approach 1: Triple Pass with List Comparisons (Brute Force)

The most straightforward approach: check each constraint separately using list comparisons.

```python
from typing import List

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # Check all rows
        for row in board:
            digits = [x for x in row if x != "."]
            if len(digits) != len(set(digits)):
                return False

# Check all columns
        for col in range(9):
            digits = [board[row][col] for row in range(9) if board[row][col] != "."]
            if len(digits) != len(set(digits)):
                return False

# Check all 3x3 boxes
        for box_row in range(0, 9, 3):
            for box_col in range(0, 9, 3):
                digits = []
                for r in range(box_row, box_row + 3):
                    for c in range(box_col, box_col + 3):
                        if board[r][c] != ".":
                            digits.append(board[r][c])
                if len(digits) != len(set(digits)):
                    return False

return True
```

**Time Complexity:** O(n²) where n = 9

**Space Complexity:** O(n) for temporary storage of digits in each check.

### Approach 2: Matrix Transformation Approach

Transform the board into different views (transpose for columns, reorganize for boxes) and validate each.

```python
from typing import List

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # Check rows
        if not self.check_rows(board):
            return False

# Check columns (transpose then check rows)
        transposed = self.transpose(board)
        if not self.check_rows(transposed):
            return False

# Check 3x3 boxes (reorganize then check rows)
        boxes = self.extract_boxes(board)
        if not self.check_rows(boxes):
            return False

return True

def check_rows(self, matrix: List[List[str]]) -> bool:
        for row in matrix:
            seen = set()
            for val in row:
                if val == ".":
                    continue
                if val in seen:
                    return False
                seen.add(val)
        return True

def transpose(self, board: List[List[str]]) -> List[List[str]]:
        result = [['.' for _ in range(9)] for _ in range(9)]
        for r in range(9):
            for c in range(9):
                result[c][r] = board[r][c]
        return result

def extract_boxes(self, board: List[List[str]]) -> List[List[str]]:
        result = []
        for box_row in range(0, 9, 3):
            for box_col in range(0, 9, 3):
                box = []
                for r in range(box_row, box_row + 3):
                    for c in range(box_col, box_col + 3):
                        box.append(board[r][c])
                result.append(box)
        return result
```

**Time Complexity:** O(n²)

**Space Complexity:** O(n²)

### Approach 3: Single-Pass with Hash Sets (Optimal)

Use hash sets to track seen values in rows, columns, and boxes simultaneously in one pass.

```python
from typing import List

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # Initialize sets for tracking
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

# Single pass through the board
        for r in range(9):
            for c in range(9):
                val = board[r][c]

# Skip empty cells
                if val == ".":
                    continue

# Calculate which 3x3 box this cell belongs to
                box_idx = (r // 3) * 3 + (c // 3)

# Check if we've seen this value before
                if val in rows[r] or val in cols[c] or val in boxes[box_idx]:
                    return False

# Mark as seen
                rows[r].add(val)
                cols[c].add(val)
                boxes[box_idx].add(val)

return True
```

**Time Complexity:** O(n²) where n = 9

**Space Complexity:** O(n²)

### Approach 4: String Encoding with Single Set (Alternative)

Use string encoding to store (value, location) tuples in a single set.

```python
from typing import List

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

for r in range(9):
            for c in range(9):
                val = board[r][c]

if val == ".":
                    continue

# Create unique identifiers
                row_key = f"{val} in row {r}"
                col_key = f"{val} in col {c}"
                box_key = f"{val} in box {r//3},{c//3}"

# Check if any identifier already exists
                if row_key in seen or col_key in seen or box_key in seen:
                    return False

# Add all identifiers
                seen.add(row_key)
                seen.add(col_key)
                seen.add(box_key)

return True
```

**Time Complexity:** O(n²)

**Space Complexity:** O(n²)

## Key Takeaways

01. **Hash sets provide O(1) duplicate detection** 
02. **Single-pass algorithms are more efficient**
03. **Coordinate mapping is crucial**
04. **Understand constraint validation deeply**
05. **Real systems need more than correctness** 
06. **Early termination is valuable** 
07. **Know when to optimize and when not to**

### Complexity Summary Table

| Approach | Time | Space | Passes | Best For |
| --- | --- | --- | --- | --- |
| Triple Pass with Lists | O(n²) | O(n) | 3 | Learning/debugging |
| Matrix Transformation | O(n²) | O(n²) | 3 | Code reuse emphasis |
| Single-Pass Hash Sets | O(n²) | O(n²) | 1 | Production code |
| String Encoding | O(n²) | O(n²) | 1 | Readability/extensibility |