DSA Patterns
Viewed better in dark mode.
No. Pattern Description Key Idea Example
1 Sliding Window Used for problems Use a sliding Longest Substring
involving window to Without Repeating
subarrays or optimize time Characters
substrings. complexity from
O(n^2) to O(n). Maximum Sum
Subarray of Size K
2 Two Pointers Used for problems Use two pointers Two Sum (Sorted
involving sorted moving Array)
arrays, linked lists, towards/away
or string from each other. Trapping Rainwater
manipulation.
3 Fast and Slow Used for cyclic Use two pointers Linked List Cycle
Pointers problems like moving at Detection
finding loops in different speeds.
linked lists. Middle of a Linked
List
4 Merge Intervals Used for problems Sort intervals and Merge Intervals
involving merge based on
overlapping conditions. Insert Interval
intervals.
5 Cyclic Sort Used for problems Place each number Missing Number
involving numbers at its correct
in a given range (1 index. Find All Duplicate
to n). Numbers
6 Subsets Used for problems Use BFS, Generate All
requiring all recursion, or Subsets
combinations/sub bitmasking.
sets of elements. Generate
Permutations
7 Binary Search Used for searching Divide and Search in Rotated
in sorted arrays or conquer; halve the Sorted Array
answer-based search space.
problems. Find Peak Element
8 Backtracking Used for Try all possibilities N-Queens
constraint-based and backtrack
problems like upon failure. Word Search
permutations and
combinations.
9 Breadth-First Used for shortest Explore all Binary Tree Level
Search (BFS) path or level-order neighbors at the Order Traversal
traversal problems. current level
before moving to Word Ladder
the next level.
10 Depth-First Used for Recursively or All Paths in a Graph
Search (DFS) pathfinding, iteratively explore
tree/graph each path fully. Number of Islands
traversal, and
connected
components.
11 Topological Sort Used for problems Use BFS or DFS to Course Schedule
with dependencies order tasks based
in a Directed on prerequisites. Alien Dictionary
Acyclic Graph
(DAG).
12 Union-Find Used for Use union and find Number of
(Disjoint Set) connectivity in operations to Connected
graphs. manage connected Components
components.
Redundant
Connection
13 Greedy Used for Make the locally Interval Scheduling
optimization optimal choice at
problems each step. Huffman Encoding
(minimizing/maxi
mizing something).
14 Dynamic Used for Break the problem Longest Increasing
Programming optimization and into overlapping Subsequence
(DP) decision-based subproblems. 0/1 Knapsack
problems.
15 Bit Manipulation Used for Use bitwise Single Number
binary-related operators to solve
problems like efficiently. Power of Two
subsets and XOR.
16 Matrix Traversal Used for problems Use BFS, DFS, or Unique Paths
involving grid dynamic
traversal. programming. Rotting Oranges
17 Heap / Priority Used for problems Use heaps for Kth Largest
Queue requiring frequent efficient insertion Element
max/min and extraction.
operations. Merge K Sorted
Lists
18 Divide and Used for problems Divide the Merge Sort
Conquer involving problem into
partitioning. smaller Median of Two
subproblem Sorted Arrays
19 Prefix Sum Used for problems Precompute Subarray Sum
involving range cumulative sums Equals K
sums. to optimize
queries. Range Sum Query
(Immutable)
20 Sliding Window Used for problems Use a sliding Longest Substring
involving window to Without Repeating
subarrays or optimize time Characters
substrings. complexity from
O(n^2) to O(n). Maximum Sum
Subarray of Size K
21 Kadane’s Used for maximum Maintain a running Maximum Subarray
Algorithm subarray problems. sum and update Sum
the max sum.
Maximum Circular
Subarray
22 Trie (Prefix Tree) Used for Use a tree Implement Trie
word-related structure for fast
problems. prefix lookups. Word Search II
23 Segment Trees Used for range Build a tree Range Sum Query
query problems. structure for
efficient range Range Minimum
queries and Query
updates.
24 Graph Traversal Used for Use DFS, BFS, or Shortest Path in
graph-related Dijkstra's Weighted Graph
problems like algorithm.
shortest paths or Minimum Spanning
connected Tree
components.
25 Flood Fill Used for Use DFS or BFS to Flood Fill
grid-based visit all connected
coloring or components Number of Enclaves
connected regions.
26 Monotonic Stack Used for problems Use a stack to Next Greater
involving nearest maintain a Element
larger/smaller monotonic Largest Rectangle
elements. sequence. in Histogram
27 String Matching Used for finding Use efficient string Substring Search
(KMP, substrings in a matching
Rabin-Karp) string. algorithms. Shortest
Palindrome
28 Binary Indexed Used for dynamic Use a tree Range Sum Query
Tree (Fenwick range structure to
Tree) sum/updates. efficiently Count of Smaller
compute prefix Numbers After Self
sums.
29 Reservoir Used for random Keep track of k Random Node in a
Sampling sampling. items randomly Linked List
while iterating.
Random Sampling|
30 LRU Cache Used for caching Use a hashmap LRU Cache
problems. and doubly linked Implementation
list.
LFU Cache
31 Fibonacci Used for DP Compute Climbing Stairs
Sequence problems. Fibonacci numbers
iteratively or using House robbers
matrix
exponentiation.
32 Game Theory Used for Use minimax or DP Nim Game
competitive game to determine the
problems. winner. Predict the Winner
33 Mathematical Used for number Use properties of GCD and LCM|
Problems theory and numbers for
combinatorics. optimization. Combination Sum
