Pattern Documentation Index¶

2025-12-102026-01-09

Auto-generated from: ontology/ + meta/patterns/
Generator: tools/patterndocs/generate_pattern_docs.py

This directory contains comprehensive documentation for each API Kernel and its associated problem-solving Patterns. Each document serves as a complete reference for understanding, implementing, and applying these patterns.

How to Use This Documentation¶

Each pattern provides two learning paths to help you master the concepts:

Path	Purpose	Best For
💡 Intuition	Understand the "why" through stories and visual explanations	First-time learners, building mental models
🛠️ Templates	Production-ready implementations with problem-specific variations	Interview prep, quick reference

Recommended approach: Start with Intuition to build understanding, then use Templates for implementation.

Available Pattern Guides¶

API Kernel	Learning Resources	Description	Problems
`SubstringSlidingWindow`	💡 Intuition · 🛠️ Templates	Dynamic window over sequences	LeetCode 3, 76, 209, 239, 340, 438, 567
`TwoPointersTraversal`	💡 Intuition · 🛠️ Templates	Two pointer traversal patterns	LeetCode 11, 15, 16, 26, 27, 75, 80, 88, 125, 141, 142, 167, 202, 283, 287, 680, 876, 977
`BinarySearchBoundary`	💡 Intuition · 🛠️ Templates	Binary search boundaries	LeetCode 4, 33, 34, 35, 81, 162, 875, 1011
`BacktrackingExploration`	💡 Intuition · 🛠️ Templates	Exhaustive search with pruning	LeetCode 39, 40, 46, 47, 51, 52, 77, 78, 79, 90, 93, 131, 216
`MonotonicStack`	💡 Intuition · 🛠️ Templates	Boundary resolution via monotonicity	LeetCode 42, 84, 85, 316, 321, 402, 496, 503, 739, 901, 907
`PrefixSum`	💡 Intuition · 🛠️ Templates	Range queries and subarray sums	LeetCode 238, 303, 304, 523, 525, 560, 1094, 1109
`Heap`	💡 Intuition · 🛠️ Templates	Top-K, median, scheduling	LeetCode 23, 215, 253, 295, 347, 621, 1046
`GraphDFS` / `GraphBFS`	💡 Intuition · 🛠️ Templates	Graph traversal patterns	LeetCode 133, 200, 286, 417, 542, 547, 785, 841, 994
`IntervalMerge` / `IntervalScheduling`	💡 Intuition · 🛠️ Templates	Interval merge and scheduling	LeetCode 56, 57, 435, 452, 986
`UnionFindConnectivity`	💡 Intuition · 🛠️ Templates	Disjoint set connectivity	LeetCode 547, 684, 721, 990, 1319
`TreeTraversalDFS` / `TreeTraversalBFS`	💡 Intuition · 🛠️ Templates	Tree DFS/BFS and path problems	LeetCode 94, 102, 104, 110, 124, 337, 543, 968
`TopologicalSort`	💡 Intuition · 🛠️ Templates	Dependency ordering and cycle detection	LeetCode 207, 210, 802, 1203
`ShortestPath`	💡 Intuition · 🛠️ Templates	Dijkstra, 0-1 BFS, Bellman-Ford	LeetCode 743, 787, 1368, 1631
`Trie`	💡 Intuition · 🛠️ Templates	Prefix tree operations, autocomplete	LeetCode 208, 211, 212, 648, 1268
`GreedyCore`	💡 Intuition · 🛠️ Templates	Non-interval, non-heap greedy invariants	LeetCode 45, 55, 134, 135, 455, 1029
`DP1DLinear`	💡 Intuition · 🛠️ Templates	1D dynamic programming backbone	LeetCode 70, 121, 198, 213, 746
`DPKnapsackSubset`	💡 Intuition · 🛠️ Templates	0/1 and unbounded knapsack patterns	LeetCode 322, 416, 494, 518
`MathNumberTheory`	💡 Intuition · 🛠️ Templates	GCD, primes, modular arithmetic, base conversion	LeetCode 168, 204
`SegmentTreeFenwick`	💡 Intuition · 🛠️ Templates	Range queries with updates, inversion counting	LeetCode 307, 315, 327
`LineSweep`	💡 Intuition · 🛠️ Templates	Event counting, capacity tracking, height tracking	LeetCode 218, 253, 1094, 1109
`TreeDP`	💡 Intuition · 🛠️ Templates	Include/exclude, path contribution, multi-state	LeetCode 124, 337, 968
`BitmaskDP`	💡 Intuition · 🛠️ Templates	Subset enumeration, BFS with bitmask, set cover	LeetCode 78, 847, 1125
`StringDP`	💡 Intuition · 🛠️ Templates	LCS, edit distance, palindrome, regex matching	LeetCode 10, 44, 72, 516
`MonotonicDeque`	💡 Intuition · 🛠️ Templates	Sliding window min/max, bounded range, prefix sum optimization	LeetCode 239, 862
`IntervalDP`	💡 Intuition · 🛠️ Templates	Burst balloons, polygon triangulation, cut stick, strange printer	LeetCode 312, 664, 1039, 1547
`GridBFSMultiSource`	💡 Intuition · 🛠️ Templates	Multi-source BFS on grids	LeetCode 286, 542, 994
`KWayMerge`	💡 Intuition · 🛠️ Templates	Merge K sorted sequences	LeetCode 21, 23, 88
`LinkedListInPlaceReversal`	💡 Intuition · 🛠️ Templates	In-place linked list reversal	LeetCode 25, 92, 206
`StringMatching`	💡 Intuition · 🛠️ Templates	KMP, Rabin-Karp, pattern matching	LeetCode 28, 214, 459, 1392
`GameTheoryDP`	💡 Intuition · 🛠️ Templates	Minimax, optimal play, game states	LeetCode 486, 877, 1406

Document Structure¶

Each pattern document follows a consistent structure:

1. Header
   - API Kernel name and core mechanism
   - Overview of the pattern family

2. Core Concepts
   - Fundamental principles
   - Universal template structure
   - Strategy variants (maximize/minimize/fixed)

3. Base Template Problem
   - The "ancestor" problem that defines the pattern
   - Complete implementation with detailed comments
   - Algorithm explanation and trace examples

4. Variation Problems
   - Each variation shows:
     - Problem statement and invariant
     - Delta from base template (what changes)
     - Complete implementation
     - Key insights

5. Comparison Table
   - Side-by-side comparison of all variations

6. Decision Guide
   - When to use this pattern
   - Decision flowchart

7. Quick Reference Templates
   - Copy-paste ready templates

Source Files¶

Pattern documentation is composed from:

meta/
└── patterns/
    └── <api_kernel_id>/
        ├── _header.md        # Core concepts
        ├── _comparison.md    # Comparison table
        ├── _decision.md      # When to use
        ├── _templates.md     # Quick reference
        └── XXXX-<name>.md    # Per-problem snippets

Example: Sliding Window¶

meta/patterns/sliding_window/
├── _config.toml             # File ordering configuration (optional)
├── _header.md               # Invariant, template structure, strategies
├── _comparison.md           # Pattern comparison table
├── _decision.md             # When to use sliding window
├── _templates.md            # Maximize/minimize/fixed templates
├── 0003-base.md             # LeetCode 3 - Base template
├── 0076-min-window.md       # LeetCode 76 - Minimum Window Substring
├── 0209-min-subarray.md     # LeetCode 209 - Minimum Size Subarray Sum
├── 0340-k-distinct.md       # LeetCode 340 - At Most K Distinct
├── 0438-anagrams.md         # LeetCode 438 - Find All Anagrams
└── 0567-permutation.md      # LeetCode 567 - Permutation in String

File Ordering Configuration¶

Each pattern directory can include a _config.toml file to control the order of files in the final document:

# meta/patterns/<pattern_name>/_config.toml
header_files = ["_header.md"]
problem_files = ["0003-base.md", "0076-min-window.md", "0209-min-subarray.md", ...]
footer_files = ["_comparison.md", "_decision.md", "_templates.md"]

If _config.toml exists: Files are ordered exactly as specified
If _config.toml doesn't exist: Falls back to default ordering (alphabetical for problems)

See meta/patterns/README.md for detailed documentation.

Generating Documentation¶

To regenerate pattern documentation:

python tools/patterndocs/generate_pattern_docs.py

Options:

# Generate specific pattern
python tools/patterndocs/generate_pattern_docs.py --pattern sliding_window

# Generate all patterns
python tools/patterndocs/generate_pattern_docs.py --all

# Validate only (no write)
python tools/patterndocs/generate_pattern_docs.py --validate

Adding New Patterns¶

1. Define in Ontology¶

Add the API Kernel in ontology/api_kernels.toml:

[[api_kernels]]
id = "NewKernel"
summary = "Description of the kernel mechanism."

Add patterns in ontology/patterns.toml:

[[patterns]]
id = "new_pattern_variant"
api_kernel = "NewKernel"
summary = "Description of this specific pattern."

2. Create Source Files¶

Create directory and files in meta/patterns/:

meta/patterns/new_kernel/
├── _header.md
├── _comparison.md
├── _decision.md
├── _templates.md
└── XXXX-problem.md

3. Generate Documentation¶

python tools/patterndocs/generate_pattern_docs.py --pattern new_kernel

Relationship to Problem Metadata¶

Each problem in meta/problems/*.toml references patterns:

# meta/problems/0003_longest_substring_without_repeating_characters.toml
api_kernels = ["SubstringSlidingWindow"]
patterns    = ["sliding_window_unique"]

[pattern_role]
is_base_template = true
base_for_kernel  = "SubstringSlidingWindow"
derived_problems = ["0076", "0159", "0209", "0340", "0438", "0567"]

The generator uses this metadata to: - Order problems correctly (base first, then variations) - Generate cross-references - Build the comparison table automatically

Last updated: Auto-generated by tools/patterndocs/generate_pattern_docs.py