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:

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.

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.

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.

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.

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

1. Hash sets provide O(1) duplicate detection
2. Single-pass algorithms are more efficient
3. Coordinate mapping is crucial
4. Understand constraint validation deeply
5. Real systems need more than correctness
6. Early termination is valuable
7. Know when to optimize and when not to

Complexity Summary Table