🧠 Data Structures & Algorithms — The Complete Pattern Bible

🚀 Explore the Interactive Living Documentation Portal: https://vadde.github.io/DSA/
Complete interactive architecture with 44 patterns, 14 engines, 460 isolated visual diagrams, full-text Cmd+K search, SIFT simulator, and multi-theme cosmic liquid-glass UI.

"You don't need to memorize 43 patterns. You need to memorize 5 questions, 7 families, and 1 mantra."

---

🏛️ The Three Pillars of Mastery

┌───────────────────────────────────────────────────────────────────────────────┐
│ 🏛️ PILLAR 0: THEORETICAL FOUNDATIONS (The Physics of Computation)             │
│ Computability (Turing/Rice) • Complexity Zoo (P, NP, PSPACE) • Lower Bounds   │
│ Asymptotics • Amortization • Approximations • Heuristics • Engineering Triage │
│ 📂 00 - Fundamentals/000 - Theoretical Foundations (The Complete Guide)/      │
└───────────────────────────────────────┬───────────────────────────────────────┘
                                       ▼
┌──────────────────────────────────────────────────────────────────────────────┐
│ ⚙️ PILLAR 1: DATA STRUCTURE ENGINE ROOMS (The Concrete Mechanics)             │
│ Stacks • Queues • Linked Lists • Heaps • BSTs • Tries • Trees • Graphs       │
│ 📂 00 - Fundamentals/ (001 - 014 Engines, 015 Trees Guide, 016 Graphs Guide) │
└──────────────────────────────────────┬───────────────────────────────────────┘
                                       ▼
┌─────────────────────────────────────────────────────────────────────────────┐
│ ⚔️ PILLAR 2: ALGORITHMIC PATTERNS (The Tactical Arsenal)                     │
│ 43 Patterns • SIFT Method • 7 Pattern Families • Muscle Memory Skeletons    │
│ 📂 01 - Warmup/ ... 43 - Miscellaneous/                                     │
└─────────────────────────────────────────────────────────────────────────────┘

---

🔑 The SIFT Method — Your 10-Second Pattern Finder

Before writing a single line of code, say this out loud:

"My input is a ____. I need to find ____. The constraint is ____. Therefore, the pattern is ____."

• State the problem in your own words
• Identify the input type and constraints
• Find the pattern using the trigger words below
• Template: Write the skeleton code from memory

---

🗺️ The Master Decision Flowchart

Read the problem → Ask Question 1 → Narrow → Ask Question 2 → Solve.

flowchart TD
    START["📖 Read the Problem"] --> Q1{"❓ What is the INPUT?"}
    
    Q1 -->|"Sorted Array"| SA["🔍 Binary Search\n👉 Two Pointers"]
    Q1 -->|"Unsorted Array / String"| UA{"❓ What do you need?"}
    Q1 -->|"Linked List"| LL["🐢 Fast & Slow\n🔄 In-place Reversal\n📋 Clone"]
    Q1 -->|"Tree"| TR{"❓ Level-by-level\nor Path-by-path?"}
    Q1 -->|"Graph / Matrix"| GR{"❓ What to find?"}
    Q1 -->|"Intervals"| IV["📐 Merge Intervals\n🤑 Greedy"]
    Q1 -->|"Numbers / Bits"| BT["⊕ Bitwise XOR"]
    
    UA -->|"Subarray (contiguous)"| SUB["🪟 Sliding Window\n➕ Prefix Sum"]
    UA -->|"Pair / Triplet"| TP["👉 Two Pointers (sort first!)"]
    UA -->|"Missing / Duplicate in [1,N]"| CS["🔢 Cyclic Sort"]
    UA -->|"Next Greater / Smaller"| MS["📊 Monotonic Stack"]
    UA -->|"All combos / permutations"| BK["🔙 Backtracking\n📦 Subsets"]
    UA -->|"Kth largest / smallest"| TK["🏆 Top K / Heap"]
    UA -->|"Count ways / Optimize"| DP["🧮 Dynamic Programming"]
    UA -->|"Lookup / Frequency"| HM["#️⃣ Hash Map"]
    
    TR -->|"Level-by-level"| BFS["🌊 Tree BFS (Queue)"]
    TR -->|"Path / Depth"| DFS["🌲 Tree DFS (Recursion)"]
    
    GR -->|"Connected groups"| UF["🔗 Union Find"]
    GR -->|"Task ordering"| TS["📋 Topological Sort"]
    GR -->|"Islands / Flood fill"| IS["🏝️ Island Traversal"]
    GR -->|"Critical edges"| AP["🌉 Articulation Points"]
    
    style START fill:#1a1a2e,color:#fff,stroke:#e94560
    style Q1 fill:#16213e,color:#fff,stroke:#0f3460
    style SA fill:#0f3460,color:#fff
    style LL fill:#0f3460,color:#fff
    style IV fill:#0f3460,color:#fff
    style BT fill:#0f3460,color:#fff
    style SUB fill:#533483,color:#fff
    style TP fill:#533483,color:#fff
    style CS fill:#533483,color:#fff
    style MS fill:#533483,color:#fff
    style BK fill:#533483,color:#fff
    style TK fill:#533483,color:#fff
    style DP fill:#533483,color:#fff
    style HM fill:#533483,color:#fff
    style BFS fill:#2b2d42,color:#fff
    style DFS fill:#2b2d42,color:#fff
    style UF fill:#e94560,color:#fff
    style TS fill:#e94560,color:#fff
    style IS fill:#e94560,color:#fff
    style AP fill:#e94560,color:#fff

Loading

---

⚡ Engineering Triage: When to Go "Kill Mode" vs "Pull the Plug"

"Amateurs guess algorithms. Professionals inspect constraints, classify the complexity class, and decide instantly whether to optimize to the metal or switch to an approximation."

Input Constraint ($N$)	Allowed Complexity	Tactical Mindset	Strategic Move
$N \le 10$	$O(N!) \text{ or } O(N^6)$	🔙 Permutations / Backtracking	Brute-force DFS, state permutations (itertools.permutations)
$N \le 20$	$O(2^N \cdot N)$	🧩 Bitmask DP / Subsets	Meet-in-the-Middle, State compression DP, Subsets
$N \le 100$	$O(N^4)$	🧮 2D/3D DP / Floyd-Warshall	High-dimensional Dynamic Programming
$N \le 500$	$O(N^3)$	🌊 Matrix Multiplication / Floyd	Triple nested loops, all-pairs shortest paths
$N \le 5,000$	$O(N^2)$	🪟 Nested Loops / 2D DP	Quadratic DP, nested scans, Kadane variants
$N \le 10^5$	$O(N \log N)$	🚀 KILL MODE: Sort / Heap / Tree	Sorting, Divide-and-Conquer, Segment Trees, Heaps
$N \le 10^6$	$O(N)$	⚡ KILL MODE: Linear Scan	Sliding Window, Hash Map, Two Pointers, Monotonic Stack
$N \ge 10^9$	$O(\log N) \text{ or } O(1)$	🎯 Math / Binary Search	Binary Search over answer, Bitwise tricks, Closed-form math

🚨 The Decision Rule:

• Problem is in $P$ (or $N$ fits the table) $\longrightarrow$ 🔥 GO KILL MODE: Derive the exact optimal pattern, eliminate allocations, exploit CPU cache locality, and nail the proof.
• Problem is $NP$-Hard and $N > 30$ $\longrightarrow$ 🛑 PULL THE PLUG: Stop searching for polynomial exact algorithms ($P \ne NP$). Switch to Approximations (Ch 7), Randomization (Ch 8), or Metaheuristics (Ch 9).
• Need the full engineering decision framework? Explore 000 - Chapter 12: Kill Mode vs Pull the Plug.

---

👨‍👩‍👧‍👦 The 7 Pattern Families

Don't memorize 43 patterns. Memorize 7 families. Each family shares the same "feeling".

mindmap
  root((🧠 DSA Patterns))
    🏃 Runners
      Two Pointers
      Fast & Slow
      Sliding Window
    📦 Sorters
      Merge Intervals
      Cyclic Sort
      Linear Sort
    🌲 Explorers
      Tree BFS
      Tree DFS
      Island Traversal
      Backtracking
    📊 Rankers
      Top K Elements
      Two Heaps
      K-way Merge
    🔍 Searchers
      Binary Search
      Trie
      Hash Maps
    🧮 Counters
      Prefix Sum
      DP: Knapsack
      DP: Fibonacci
      DP: Palindrome
      Segment Tree
      BIT
    🔗 Connectors
      Union Find
      Topological Sort
      Clone
      Serialize

Loading

Family	Core Idea	When Your Gut Says...
🏃 Runners	Two things moving through data	"I need to scan with a window or shrink from both sides"
📦 Sorters	Put things in the right place	"Things overlap or belong at specific positions"
🌲 Explorers	Visit nodes, explore paths	"I need to traverse a tree, graph, or grid"
📊 Rankers	Find the best K things	"I need the top/bottom K or a running median"
🔍 Searchers	Find something fast	"I need to look up, match, or search efficiently"
🧮 Counters	Count or accumulate values	"I need to count ways, sums, or optimize a value"
🔗 Connectors	Manage relationships	"Things are connected, ordered, or need to be copied"

---

🎯 Trigger Word → Pattern (Instant Lookup)

Scan the problem statement. Spot ONE of these phrases. You have your pattern.

🏃 Runner Patterns

🔍 When You See...	💡 Instantly Think...	🏷️ Pattern
"pair", "triplet", "two sum", "sorted array"	Shrink from both ends	Two Pointers
"cycle in linked list", "middle of list", "happy number"	Tortoise 🐢 and Hare 🐇	Fast & Slow
"longest substring", "K distinct characters", "window"	Expand right, shrink left	Sliding Window

📦 Sorter Patterns

🔍 When You See...	💡 Instantly Think...	🏷️ Pattern
"merge intervals", "overlapping meetings"	Sort by start, merge greedily	Merge Intervals
"missing number", "duplicate in [1,N]", "first missing positive"	Each number IS its own index	Cyclic Sort

🌲 Explorer Patterns

🔍 When You See...	💡 Instantly Think...	🏷️ Pattern
"level order", "zigzag traversal", "right side view"	Queue + level_size loop	Tree BFS
"max depth", "path sum", "diameter", "LCA"	Recurse left + right	Tree DFS
"number of islands", "flood fill", "surrounded regions"	DFS/BFS on grid, mark visited	Island Traversal
"N-Queens", "generate parentheses", "sudoku", "permutations"	Choose → Explore → Un-choose	Backtracking

📊 Ranker Patterns

🔍 When You See...	💡 Instantly Think...	🏷️ Pattern
"Kth largest", "K closest points", "top K frequent"	Min-heap of size K	Top K Elements
"median of stream", "balance two halves"	Max-heap (left) + Min-heap (right)	Two Heaps
"merge K sorted lists/arrays"	Min-heap holding K heads	K-way Merge

🔍 Searcher Patterns

🔍 When You See...	💡 Instantly Think...	🏷️ Pattern
"sorted", "rotated sorted", "search in...", "minimum in rotated"	Cut search space in half	Binary Search
"autocomplete", "word search II", "prefix match"	Character-by-character tree	Trie
"frequency", "seen before", "contains duplicate"	O(1) lookup dictionary	Hash Map

🧮 Counter Patterns

🔍 When You See...	💡 Instantly Think...	🏷️ Pattern
"subarray sum equals K", "range sum"	prefix[j] − prefix[i] = K	Prefix Sum
"coin change", "subset sum", "0/1 knapsack"	Include or Exclude with memo	0-1 Knapsack DP
"climb stairs", "house robber", "decode ways"	dp[i] = dp[i−1] + dp[i−2]	Fibonacci DP
"longest palindromic subsequence"	2D DP on substring s[i..j]	Palindromic DP
"range sum query — mutable"	Array-backed tree	Segment Tree / BIT

🔗 Connector Patterns

🔍 When You See...	💡 Instantly Think...	🏷️ Pattern
"connected components", "redundant edge", "accounts merge"	find() + union()	Union Find
"course schedule", "build order", "task dependencies"	In-degree + BFS queue	Topological Sort
"clone graph", "copy list with random pointer"	Old → New HashMap	Clone
"serialize/deserialize tree"	Pre-order + null markers	Serialize

⚡ Other Instant Triggers

🔍 When You See...	💡 Instantly Think...	🏷️ Pattern
"reverse linked list", "reverse between positions"	prev / curr / next dance	In-place Reversal
"next greater element", "daily temperatures"	Decreasing stack, pop when bigger	Monotonic Stack
"sliding window maximum / minimum"	Deque keeping decreasing order	Monotonic Queue
"single number", "XOR"	a ⊕ a = 0	Bitwise XOR
"critical connections", "bridges in graph"	Tarjan's disc/low DFS	Articulation Points

---

🧬 Pattern DNA Cards — The Core Skeletons

Once you identify the pattern, recall its skeleton. Every problem in that pattern uses the SAME bones.

🏃 Two Pointers

left, right = 0, len(nums) - 1
while left < right:
    if condition:   left += 1
    else:           right -= 1

🐢 Fast & Slow

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# slow is now at the middle (or meeting point if cycle)

🪟 Sliding Window

left = 0
for right in range(len(nums)):
    # expand: add nums[right] to window
    while window_is_invalid:
        # shrink: remove nums[left], left += 1
    result = max(result, right - left + 1)

📊 Monotonic Stack

stack = []  # store INDICES, not values
for i in range(len(nums)):
    while stack and nums[stack[-1]] < nums[i]:
        result[stack.pop()] = nums[i]
    stack.append(i)

🔍 Binary Search

lo, hi = 0, len(nums) - 1
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] == target:  return mid
    elif nums[mid] < target: lo = mid + 1
    else:                    hi = mid - 1

🌊 Tree BFS

queue = deque([root])
while queue:
    for _ in range(len(queue)):  # process ONE level
        node = queue.popleft()
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)

🌲 Tree DFS

def dfs(node):
    if not node: return BASE_CASE
    left = dfs(node.left)
    right = dfs(node.right)
    return COMBINE(left, right, node.val)

🧮 Dynamic Programming

# Step 1: WHAT does dp[i] mean?
# Step 2: HOW does dp[i] relate to dp[i-1]?
# Step 3: WHAT is dp[0]?
dp = [BASE] * (n + 1)
for i in range(1, n + 1):
    dp[i] = TRANSITION(dp[i-1], dp[i-2], ...)

🔙 Backtracking

def backtrack(path, choices):
    if GOAL_REACHED:
        result.append(path[:])
        return
    for choice in choices:
        path.append(choice)        # ✅ CHOOSE
        backtrack(path, next)      # 🔄 EXPLORE
        path.pop()                 # ↩️ UN-CHOOSE

📋 Topological Sort

# Build in_degree map. Start with all nodes that have in_degree == 0.
queue = deque([n for n in graph if in_degree[n] == 0])
while queue:
    node = queue.popleft()
    result.append(node)
    for neighbor in graph[node]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            queue.append(neighbor)
# if len(result) != total_nodes → CYCLE EXISTS

🔗 Union Find

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # path compression
    return parent[x]

def union(x, y):
    px, py = find(x), find(y)
    if rank[px] < rank[py]: px, py = py, px
    parent[py] = px

---

🚨 The 10 Interview-Killing Mistakes

#	❌ The Mistake	✅ The Fix
1	Jumping to code without understanding	Spend 3 min asking questions. Restate the problem.
2	Ignoring edge cases (empty, single, all-same)	Write 3 edge cases BEFORE coding.
3	Off-by-one in Binary Search	Drill lo <= hi + lo + (hi-lo)//2 until muscle memory.
4	Not marking visited in BFS/DFS	Mark BEFORE adding to queue, not after popping.
5	Wrong DP state definition	If your transition feels forced, your state is wrong.
6	Two Pointers on unsorted array	Sort first. Always. (Except linked lists.)
7	Confusing Subarray vs Subsequence	Sub-array = contiguous → Sliding Window. Sub-sequence = not → DP.
8	Modifying collection while iterating	Use indices, or build a separate list.
9	Forgetting about negative numbers	Sliding Window usually needs all positives.
10	50+ lines of code	Step back. You're probably missing a simpler pattern.

---

📚 The Pattern Index

• 00 - Fundamentals
  • 000 - Theoretical Foundations (The Complete Guide)
  • 001 - Array and String
  • 002 - Hash Table
  • 003 - Recursion and the Call Stack
  • 004 - Sorting Algorithms
  • 005 - Queue and Stack
  • 006 - Linked List
  • 007 - Doubly Linked List
  • 008 - Circular Linked List
  • 009 - Binary Search Tree
  • 010 - Min and Max Heap
  • 011 - Trie
  • 012 - Graph
  • 013 - Union-Find (Disjoint Set)
  • 014 - Bit Manipulation
  • 015 - Trees (The Complete Guide)
  • 016 - Graphs (The Complete Guide)
  • 017 - The Pattern Cracker
  • TREES_AND_GRAPHS_GUIDE.md
• 01 - Warmup
• 02 - Two Pointers
• 03 - Fast & Slow Pointers
• 04 - Sliding Window
• 05 - Merge Intervals
• 06 - Cyclic Sort
• 07 - In-place Reversal of a LinkedList
• 08 - Stacks
• 09 - Monotonic Stack
• 10 - Hash Maps
• 11 - Tree Breadth First Search
• 12 - Tree Depth First Search
• 13 - Graphs
• 14 - Island (Matrix Traversal)
• 15 - Two Heaps
• 16 - Subsets
• 17 - Modified Binary Search
• 18 - Bitwise XOR
• 19 - Top K Elements
• 20 - K-way Merge
• 21 - Greedy Algorithms
• 22 - 0-1 Knapsack (DP)
• 23 - Fibonacci Numbers (DP)
• 24 - Palindromic Subsequence (DP)
• 25 - Backtracking
• 26 - Trie
• 27 - Topological Sort (Graph)
• 28 - Union Find
• 29 - Ordered Set
• 30 - Prefix Sum
• 31 - Multi-threaded
• 32 - Counting Pattern
• 33 - Monotonic Queue Pattern
• 34 - Simulation Pattern
• 35 - Linear Sorting Algorithm
• 36 - Meet in the Middle
• 37 - MO's Algorithm
• 38 - Serialize and Deserialize
• 39 - Clone Pattern
• 40 - Articulation Points and Bridges
• 41 - Segment Tree
• 42 - Binary Indexed Tree
• 43 - Miscellaneous