Patterns Cheat Sheet

When you see a keyword in a problem, map it to a pattern. Use this as a quick decision tool before writing any code.

---

Keyword → Pattern Map

Keywords / Problem Shape	Pattern	Complexity
Contiguous subarray, longest/shortest with condition	Sliding Window	O(n)
Sorted array, find pair summing to X	Two Pointers	O(n)
Sorted array, find target or position	Binary Search	O(log n)
All combinations / permutations / subsets	Backtracking	O(2ⁿ) / O(n!)
Number of ways to do X, min/max cost, can you reach X	Dynamic Programming	O(n) – O(n²)
Connected components, path exists, cycle in graph	Graph DFS	O(V+E)
Shortest path, BFS on grid	Graph BFS	O(V+E)
Shortest path in weighted graph (no neg weights)	Dijkstra	O((V+E)logV)
Shortest path with negative weights	Bellman-Ford	O(VE)
Task ordering, prerequisites, dependencies	Topological Sort	O(V+E)
Merge groups, detect cycle in undirected graph	Union Find	O(α(n))
Prefix search, autocomplete, starts with	Trie	O(m)
Range sum/min/max with updates	Segment Tree / Fenwick Tree	O(log n)
Repeated substring, distinct substrings	Suffix Array	O(n log n)
Sort, find kth largest, merge sorted lists	Divide & Conquer	O(n log n)
Best local choice leads to global optimum	Greedy	O(n log n)
Top K elements, kth largest/smallest	Heap	O(n log k)
Next greater element, monotonic structure	Stack	O(n)
Tree traversal in-order/pre/post	Tree DFS	O(n)
Level-order tree traversal, shortest path in tree	Tree BFS	O(n)
Insert/delete/search in sorted order	BST	O(log n)
Fast key-value lookup, counting frequencies	HashMap	O(1) avg
Reverse linked list, detect cycle, find middle	Linked List	O(n)
Base case + same structure on smaller input	Recursion	Varies

---

Decision Flowchart

Is input sorted?
  YES → Binary Search or Two Pointers
  NO  → continue

Is it a graph/tree problem?
  YES, unweighted shortest path → BFS
  YES, weighted shortest path   → Dijkstra (no neg) / Bellman-Ford (neg)
  YES, dependency/ordering      → Topological Sort
  YES, connectivity             → DFS or Union Find
  NO  → continue

Does it involve substrings/prefixes?
  YES, prefix lookup            → Trie
  YES, repeated substrings      → Suffix Array
  NO  → continue

Does it ask for ALL solutions?
  YES → Backtracking
  NO  → continue

Does it ask for count/min/max and has overlapping subproblems?
  YES → Dynamic Programming
  NO  → continue

Contiguous subarray?
  YES → Sliding Window
  NO  → continue

Top K elements?
  YES → Heap
  NO  → continue

Local best choice = global best?
  YES → Greedy

---

Common Mistake Patterns

Mistake	Correct Approach
Using O(n²) nested loops on a subarray	Sliding window
BFS on a weighted graph	Dijkstra
DFS without visited set (infinite loop)	Always track visited
DP without defining state first	Write recurrence in English first
Backtracking without pruning (TLE)	Add validity check before recursing
Greedy when DP is needed	Verify exchange argument — if greedy doesn’t provably work, use DP

---

Must-Do Rating Legend

Used in problem tables across all topic pages:

Rating	Meaning
✅	Must-do — extremely common in interviews, foundational pattern
⚡	High value — good ROI, appears in top-tier interviews
📖	Learning problem — builds intuition, less common in interviews