DSA: Patterns

1. Linear Data Structure Patterns : how to find?

(Arrays, Strings, Linked Lists)

• Sliding Window (Fixed) link
• Sliding Window (Variable)
• Two Pointers (Same Direction)
• Two Pointers (Opposite Ends)
• Fast & Slow Pointers (Cycle Detection)
• Prefix Sum
• Difference Array
• Hash Map Frequency Counting
• In-place Modification
• Sorting-based Pattern
• Cyclic Sort
• Kadane’s Algorithm (Max Subarray)
• Merge Intervals
• Interval Sweep Line
• Subarray / Subsequence Enumeration
• Monotonic Stack
• Monotonic Queue
• Counting / Bucket Sort
• Boyer–Moore Voting
• Reservoir Sampling

2. Stack & Queue Patterns

• Stack Simulation
• Monotonic Stack (Next Greater / Smaller)
• Parentheses Matching
• Expression Evaluation
• Stack for Undo / Redo
• Queue Simulation
• Deque Optimization
• Circular Queue
• Min / Max Stack
• Sliding Window using Deque

3. Tree Patterns

• Tree Traversals (Pre / In / Post)
• Level Order Traversal
• Zigzag Level Order
• Vertical Order Traversal
• DFS Path Tracking
• Root-to-Leaf Patterns
• Lowest Common Ancestor
• Diameter of Tree
• Height / Depth Calculation
• Symmetric / Mirror Tree
• Boundary Traversal
• Tree Serialisation / Deserialization
• Binary Search Tree (BST) Properties
• Tree as Graph
• Tree DP (Bottom-Up)
• Morris Traversal
• Trie-based Prefix Search
• Segment Tree
• Fenwick Tree (BIT)
• Euler Tour Technique

4. Graph & Grid Patterns

• Graph Traversal (DFS)
• Graph Traversal (BFS)
• Connected Components
• Cycle Detection (Directed)
• Cycle Detection (Undirected)
• Topological Sort (Kahn / DFS)
• Shortest Path (Unweighted)
• Shortest Path (Weighted – Dijkstra)
• Bellman-Ford
• Floyd–Warshall
• Minimum Spanning Tree (Kruskal)
• Minimum Spanning Tree (Prim)
• Union Find (DSU)
• Grid DFS / BFS
• Multi-source BFS
• Flood Fill
• Bipartite Graph Check
• Strongly Connected Components (Kosaraju / Tarjan)
• Articulation Points
• Bridges in Graph

5. Binary Search Patterns

• Classic Binary Search
• Binary Search on Answer
• First / Last Occurrence
• Peak Finding
• Rotated Sorted Array
• Lower Bound / Upper Bound
• Kth Smallest / Largest
• Search in Infinite Array
• Ternary Search
• Parametric Search

6. Dynamic Programming Patterns

• 1D DP (Linear)
• 2D DP (Grid / Matrix)
• Knapsack (0/1)
• Knapsack (Unbounded)
• Subset Sum
• Partition DP
• Coin Change
• LIS (Longest Increasing Subsequence)
• LCS (Longest Common Subsequence)
• DP on Strings
• DP on Trees
• DP on Graphs (DAG)
• Interval DP
• Bitmask DP
• Digit DP
• Probability DP
• Game Theory DP
• State Compression DP
• DP with Binary Search
• Optimization DP (Convex Hull Trick)

7. Greedy Patterns

• Activity Selection
• Interval Scheduling
• Huffman Encoding
• Greedy with Sorting
• Greedy with Heap
• Fractional Knapsack
• Job Sequencing
• Gas Station
• Candy Distribution
• Greedy on Graphs

8. Heap / Priority Queue Patterns

• Top-K Elements
• K-way Merge
• Median from Data Stream
• Sliding Window Median
• Heap + HashMap
• Two Heaps Technique
• Min-Max Heap
• Heap Sort
• Priority Scheduling
• Heap-based Graph Algorithms

9. Bit Manipulation Patterns

• XOR Tricks
• Single / Unique Number
• Bit Masking
• Subset Generation using Bits
• Bitwise DP
• Power of Two Checks
• Counting Set Bits
• Gray Code
• Bitwise Trie
• Bitwise Sliding Window

10. Backtracking & Recursion Patterns

• Generate All Combinations
• Generate All Permutations
• Subsets / Power Set
• N-Queens
• Sudoku Solver
• Palindrome Partitioning
• Combination Sum
• Word Search
• DFS with Pruning
• State Space Search

11. Mathematical & Misc Patterns

• GCD / LCM
• Modular Arithmetic
• Fast Exponentiation
• Matrix Exponentiation
• Sieve of Eratosthenes
• Number Theory Counting
• Geometry Sweep Line
• Randomized Algorithms
• Game Simulation
• String Matching (KMP / Z / Rabin-Karp)

12. Advanced / Hybrid Patterns

• Meet in the Middle
• Mo’s Algorithm
• Heavy-Light Decomposition
• Centroid Decomposition
• Persistent Data Structures
• Offline Queries
• Parallel Binary Search
• Divide & Conquer Optimization
• A* Search
• Maximum Flow (Ford-Fulkerson)
• Min-Cost Max-Flow
• Bipartite Matching
• Hungarian Algorithm
• Suffix Array
• Suffix Automaton
• Palindromic Tree (EERTREE)
• Rope Data Structure
• Treap
• Skip List
• Wavelet Tree