Complete DSA Patterns Reference Guide

🎯 Core Problem-Solving Patterns (1-31)

No.	Pattern	Description	Key Idea	Example Problems & Links
1	Sliding Window	Used for problems involving subarrays or substrings.	Use a sliding window to optimize time complexity from O(n²) to O(n).	3. Longest Substring Without Repeating Characters 209. Minimum Size Subarray Sum
2	Two Pointers	Used for problems involving sorted arrays, linked lists, or string manipulation.	Use two pointers moving towards/away from each other.	167. Two Sum II - Input Array Is Sorted 42. Trapping Rain Water
3	Fast and Slow Pointers	Used for cyclic problems like finding loops in linked lists.	Use two pointers moving at different speeds.	141. Linked List Cycle 876. Middle of the Linked List
4	Merge Intervals	Used for problems involving overlapping intervals.	Sort intervals and merge based on conditions.	56. Merge Intervals 57. Insert Interval
5	Cyclic Sort	Used for problems involving numbers in a given range (1 to n).	Place each number at its correct index.	268. Missing Number 442. Find All Duplicates in an Array
6	Subsets	Used for problems requiring all combinations/sub sets of elements.	Use BFS, recursion, or bitmasking.	78. Subsets 46. Permutations
7	Binary Search	Used for searching in sorted arrays or answer-based problems.	Divide and conquer; halve the search space.	33. Search in Rotated Sorted Array 704. Binary Search
8	Backtracking	Used for constraint-based problems like permutations and combinations.	Try all possibilities and backtrack upon failure.	51. N-Queens 79. Word Search
9	Breadth-First Search (BFS)	Used for shortest path or level-order traversal problems.	Explore all neighbors at the current level before moving to the next level.	102. Binary Tree Level Order Traversal 127. Word Ladder
10	Depth-First Search (DFS)	Used for pathfinding, tree/graph traversal and connected components.	Recursively or iteratively explore each path fully.	797. All Paths From Source to Target 200. Number of Islands
11	Topological Sort	Used for problems with dependencies in a Directed Acyclic Graph (DAG).	Use BFS or DFS to order tasks based on prerequisites.	207. Course Schedule 210. Course Schedule II
12	Union-Find (Disjoint Set)	Used for connectivity in graphs.	Use union and find operations to manage connected components.	547. Number of Provinces 684. Redundant Connection
13	Greedy	Used for optimization problems (minimizing/maximizing something).	Make the locally optimal choice at each step.	435. Non-overlapping Intervals 621. Task Scheduler
14	Dynamic Programming (DP)	Used for optimization and decision-based problems.	Break the problem into overlapping subproblems.	300. Longest Increasing Subsequence 416. Partition Equal Subset Sum
15	Bit Manipulation	Used for binary-related problems like subsets and XOR queries.	Use bitwise operators to solve efficiently.	136. Single Number 231. Power of Two
16	Matrix Traversal	Used for problems involving grid traversal.	Use BFS, DFS, or dynamic programming.	62. Unique Paths 994. Rotting Oranges
17	Heap / Priority Queue	Used for problems requiring frequent max/min operations.	Use heaps for efficient insertion and extraction.	215. Kth Largest Element in an Array 23. Merge k Sorted Lists
18	Divide and Conquer	Used for problems involving partitioning.	Divide the problem into smaller subproblems.	912. Sort an Array 4. Median of Two Sorted Arrays
19	Prefix Sum	Used for problems involving range sums.	Precompute cumulative sums to optimize queries.	560. Subarray Sum Equals K 303. Range Sum Query - Immutable
20	Sliding Window Maximum	Used for problems involving maximum/minimum in sliding windows.	Use deque to maintain window maximum efficiently.	239. Sliding Window Maximum 1425. Constrained Subsequence Sum
21	Kadane's Algorithm	Used for maximum subarray problems.	Maintain a running sum and update the max sum.	53. Maximum Subarray 918. Maximum Sum Circular Subarray
22	Trie (Prefix Tree)	Used for word-related problems.	Use a tree structure for fast prefix lookups.	208. Implement Trie (Prefix Tree) 212. Word Search II
23	Segment Trees	Used for range query problems.	Build a tree structure for efficient range queries.	307. Range Sum Query - Mutable 315. Count of Smaller Numbers After Self
24	Graph Traversal	Used for graph-related problems like shortest paths or connected components.	Use DFS, BFS, or Dijkstra's algorithm.	743. Network Delay Time 1584. Min Cost to Connect All Points
25	Flood Fill	Used for grid-based coloring or connected regions.	Use DFS or BFS to visit all connected components.	733. Flood Fill 1020. Number of Enclaves
26	Monotonic Stack	Used for problems involving nearest larger/smaller elements.	Use a stack to maintain a monotonic sequence.	496. Next Greater Element I 84. Largest Rectangle in Histogram
27	String Matching (KMP, Rabin-Karp)	Used for finding substrings in a string.	Use efficient string matching algorithms.	28. Find the Index of the First Occurrence in a String 214. Shortest Palindrome
28	Binary Indexed Tree (Fenwick Tree)	Used for dynamic range sum/updates.	Use a tree structure to efficiently compute prefix sums.	307. Range Sum Query - Mutable 315. Count of Smaller Numbers After Self
29	Reservoir Sampling	Used for random sampling.	Keep track of k items randomly selected from a stream.	382. Linked List Random Node 398. Random Pick Index
30	LRU Cache	Used for caching problems.	Use a hashmap and doubly linked list.	146. LRU Cache 460. LFU Cache
31	Fibonacci Sequence	Used for DP problems.	Compute Fibonacci numbers iteratively or using matrix exponentiation.	70. Climbing Stairs 198. House Robber

No.

Pattern

Description

Key Idea

Example Problems & Links

Sliding Window

Used for problems involving subarrays or substrings.

Use a sliding window to optimize time complexity from O(n²) to O(n).

3. Longest Substring Without Repeating Characters 209. Minimum Size Subarray Sum

Two Pointers

Used for problems involving sorted arrays, linked lists, or string manipulation.

Use two pointers moving towards/away from each other.

167. Two Sum II - Input Array Is Sorted 42. Trapping Rain Water

Fast and Slow Pointers

Used for cyclic problems like finding loops in linked lists.

Use two pointers moving at different speeds.

141. Linked List Cycle 876. Middle of the Linked List

Merge Intervals

Used for problems involving overlapping intervals.

Sort intervals and merge based on conditions.

56. Merge Intervals 57. Insert Interval

Cyclic Sort

Used for problems involving numbers in a given range (1 to n).

Place each number at its correct index.

268. Missing Number 442. Find All Duplicates in an Array

Subsets

Used for problems requiring all combinations/sub sets of elements.

Use BFS, recursion, or bitmasking.

78. Subsets 46. Permutations

Binary Search

Used for searching in sorted arrays or answer-based problems.

Divide and conquer; halve the search space.

33. Search in Rotated Sorted Array 704. Binary Search

Backtracking

Used for constraint-based problems like permutations and combinations.

Try all possibilities and backtrack upon failure.

51. N-Queens 79. Word Search

Breadth-First Search (BFS)

Used for shortest path or level-order traversal problems.

Explore all neighbors at the current level before moving to the next level.

102. Binary Tree Level Order Traversal 127. Word Ladder

Depth-First Search (DFS)

Used for pathfinding, tree/graph traversal and connected components.

Recursively or iteratively explore each path fully.

797. All Paths From Source to Target 200. Number of Islands

Topological Sort

Used for problems with dependencies in a Directed Acyclic Graph (DAG).

Use BFS or DFS to order tasks based on prerequisites.

207. Course Schedule 210. Course Schedule II

Union-Find (Disjoint Set)

Used for connectivity in graphs.

Use union and find operations to manage connected components.

547. Number of Provinces 684. Redundant Connection

Greedy

Used for optimization problems (minimizing/maximizing something).

Make the locally optimal choice at each step.

435. Non-overlapping Intervals 621. Task Scheduler

Dynamic Programming (DP)

Used for optimization and decision-based problems.

Break the problem into overlapping subproblems.

300. Longest Increasing Subsequence 416. Partition Equal Subset Sum

Bit Manipulation

Used for binary-related problems like subsets and XOR queries.

Use bitwise operators to solve efficiently.

136. Single Number 231. Power of Two

Matrix Traversal

Used for problems involving grid traversal.

Use BFS, DFS, or dynamic programming.

62. Unique Paths 994. Rotting Oranges

Heap / Priority Queue

Used for problems requiring frequent max/min operations.

Use heaps for efficient insertion and extraction.

215. Kth Largest Element in an Array 23. Merge k Sorted Lists

Divide and Conquer

Used for problems involving partitioning.

Divide the problem into smaller subproblems.

912. Sort an Array 4. Median of Two Sorted Arrays

Prefix Sum

Used for problems involving range sums.

Precompute cumulative sums to optimize queries.

560. Subarray Sum Equals K 303. Range Sum Query - Immutable

Sliding Window Maximum

Used for problems involving maximum/minimum in sliding windows.

Use deque to maintain window maximum efficiently.

239. Sliding Window Maximum 1425. Constrained Subsequence Sum

Kadane's Algorithm

Used for maximum subarray problems.

Maintain a running sum and update the max sum.

53. Maximum Subarray 918. Maximum Sum Circular Subarray

Trie (Prefix Tree)

Used for word-related problems.

Use a tree structure for fast prefix lookups.

208. Implement Trie (Prefix Tree) 212. Word Search II

Segment Trees

Used for range query problems.

Build a tree structure for efficient range queries.

307. Range Sum Query - Mutable 315. Count of Smaller Numbers After Self

Graph Traversal

Used for graph-related problems like shortest paths or connected components.

Use DFS, BFS, or Dijkstra's algorithm.

743. Network Delay Time 1584. Min Cost to Connect All Points

Flood Fill

Used for grid-based coloring or connected regions.

Use DFS or BFS to visit all connected components.

733. Flood Fill 1020. Number of Enclaves

Monotonic Stack

Used for problems involving nearest larger/smaller elements.

Use a stack to maintain a monotonic sequence.

496. Next Greater Element I 84. Largest Rectangle in Histogram

String Matching (KMP, Rabin-Karp)

Used for finding substrings in a string.

Use efficient string matching algorithms.

28. Find the Index of the First Occurrence in a String 214. Shortest Palindrome

Binary Indexed Tree (Fenwick Tree)

Used for dynamic range sum/updates.

Use a tree structure to efficiently compute prefix sums.

307. Range Sum Query - Mutable 315. Count of Smaller Numbers After Self

Reservoir Sampling

Used for random sampling.

Keep track of k items randomly selected from a stream.

382. Linked List Random Node 398. Random Pick Index

LRU Cache

Used for caching problems.

Use a hashmap and doubly linked list.

146. LRU Cache 460. LFU Cache

Fibonacci Sequence

Used for DP problems.

Compute Fibonacci numbers iteratively or using matrix exponentiation.

70. Climbing Stairs 198. House Robber

⚡ Advanced Patterns (32-50)

No.	Pattern	Description	Key Idea	Example Problems & Links
32	Morris Traversal	Used for tree traversal without extra space.	Use threading to traverse without recursion/stack.	94. Binary Tree Inorder Traversal 144. Binary Tree Preorder Traversal
33	Boyer-Moore Majority Vote	Used for finding majority elements.	Use voting algorithm to find majority in O(n) time.	169. Majority Element 229. Majority Element II
34	Rolling Hash	Used for string/array comparison problems.	Use polynomial rolling hash for efficient comparisons.	187. Repeated DNA Sequences 1044. Longest Duplicate Substring
35	Manacher's Algorithm	Used for palindrome problems.	Find all palindromes in linear time.	5. Longest Palindromic Substring 647. Palindromic Substrings
36	Catalan Numbers	Used for counting problems with nested structures.	Count valid combinations of nested elements.	22. Generate Parentheses 96. Unique Binary Search Trees
37	Game Theory (Minimax)	Used for game-playing problems.	Use minimax with alpha-beta pruning.	464. Can I Win 877. Stone Game
38	Line Sweep	Used for computational geometry problems.	Process events in sorted order.	253. Meeting Rooms II 218. The Skyline Problem
39	Shortest Path Algorithms	Used for graph path problems.	Dijkstra's, Bellman-Ford, Floyd-Warshall.	787. Cheapest Flights Within K Stops 1334. Find the City With Smallest Number of Neighbors
40	Meet in the Middle	Used for optimization when brute force is O(2^n).	Split problem space and combine results.	18. 4Sum 1755. Closest Subsequence Sum
41	Critical Connections	Used for finding critical nodes/edges in graphs.	Use DFS with low-link values (Tarjan's Algorithm).	1192. Critical Connections in a Network 1568. Minimum Days to Disconnect Island
42	Z-Algorithm	Used for string matching problems.	Find all occurrences of pattern in text in linear time.	28. Find the Index of the First Occurrence 1392. Longest Happy Prefix
43	Coordinate Compression	Used when dealing with large coordinate ranges.	Map large coordinates to smaller range.	391. Perfect Rectangle 850. Rectangle Area II
44	Convex Hull	Used for computational geometry problems.	Find the convex hull of a set of points.	587. Erect the Fence 1453. Maximum Darts Inside Circular Dartboard
45	Sqrt Decomposition	Used for range queries with updates.	Divide array into √n blocks for balanced operations.	307. Range Sum Query - Mutable 327. Count of Range Sum
46	Heavy-Light Decomposition	Used for tree path queries (Advanced).	Decompose tree into heavy and light edges.	Used in competitive programming Tree path sum queries
47	Network Flow (Max Flow)	Used for flow optimization problems.	Find maximum flow through a network.	Maximum bipartite matching Min-cut problems
48	Persistent Data Structures	Used when you need to maintain multiple versions.	Keep history of data structure modifications.	Version control systems Functional programming structures
49	Suffix Array/Tree	Used for string processing problems.	Efficient substring operations and pattern matching.	1044. Longest Duplicate Substring Advanced string algorithms
50	Aho-Corasick Algorithm	Used for multiple string matching.	Build automaton for multiple pattern matching.	1032. Stream of Characters Multiple pattern search

No.

Pattern

Description

Key Idea

Example Problems & Links

Morris Traversal

Used for tree traversal without extra space.

Use threading to traverse without recursion/stack.

94. Binary Tree Inorder Traversal 144. Binary Tree Preorder Traversal

Boyer-Moore Majority Vote

Used for finding majority elements.

Use voting algorithm to find majority in O(n) time.

169. Majority Element 229. Majority Element II

Rolling Hash

Used for string/array comparison problems.

Use polynomial rolling hash for efficient comparisons.

187. Repeated DNA Sequences 1044. Longest Duplicate Substring

Manacher's Algorithm

Used for palindrome problems.

Find all palindromes in linear time.

5. Longest Palindromic Substring 647. Palindromic Substrings

Catalan Numbers

Used for counting problems with nested structures.

Count valid combinations of nested elements.

22. Generate Parentheses 96. Unique Binary Search Trees

Game Theory (Minimax)

Used for game-playing problems.

Use minimax with alpha-beta pruning.

464. Can I Win 877. Stone Game

Line Sweep

Used for computational geometry problems.

Process events in sorted order.

253. Meeting Rooms II 218. The Skyline Problem

Shortest Path Algorithms

Used for graph path problems.

Dijkstra's, Bellman-Ford, Floyd-Warshall.

787. Cheapest Flights Within K Stops 1334. Find the City With Smallest Number of Neighbors

Meet in the Middle

Used for optimization when brute force is O(2^n).

Split problem space and combine results.

18. 4Sum 1755. Closest Subsequence Sum

Critical Connections

Used for finding critical nodes/edges in graphs.

Use DFS with low-link values (Tarjan's Algorithm).

1192. Critical Connections in a Network 1568. Minimum Days to Disconnect Island

Z-Algorithm

Used for string matching problems.

Find all occurrences of pattern in text in linear time.

28. Find the Index of the First Occurrence 1392. Longest Happy Prefix

Coordinate Compression

Used when dealing with large coordinate ranges.

Map large coordinates to smaller range.

391. Perfect Rectangle 850. Rectangle Area II

Convex Hull

Used for computational geometry problems.

Find the convex hull of a set of points.

587. Erect the Fence 1453. Maximum Darts Inside Circular Dartboard

Sqrt Decomposition

Used for range queries with updates.

Divide array into √n blocks for balanced operations.

307. Range Sum Query - Mutable 327. Count of Range Sum

Heavy-Light Decomposition

Used for tree path queries (Advanced).

Decompose tree into heavy and light edges.

Used in competitive programming Tree path sum queries

Network Flow (Max Flow)

Used for flow optimization problems.

Find maximum flow through a network.

Maximum bipartite matching Min-cut problems

Persistent Data Structures

Used when you need to maintain multiple versions.

Keep history of data structure modifications.

Version control systems Functional programming structures

Suffix Array/Tree

Used for string processing problems.

Efficient substring operations and pattern matching.

1044. Longest Duplicate Substring Advanced string algorithms

Aho-Corasick Algorithm

Used for multiple string matching.

Build automaton for multiple pattern matching.

1032. Stream of Characters Multiple pattern search

📊 Time and Space Complexity Quick Reference

Algorithm/Data Structure	Time Complexity	Space Complexity	Use Cases
Binary Search	O(log n)	O(1)	Sorted arrays, answer-based problems
Merge Sort	O(n log n)	O(n)	Stable sorting, external sorting
Quick Sort	O(n log n) avg, O(n²) worst	O(log n)	In-place sorting, average case performance
Heap Operations	O(log n) insert/delete, O(1) peek	O(n) for heap	Priority queues, top-k problems
Hash Table	O(1) avg, O(n) worst	O(n)	Fast lookups, counting, caching
DFS/BFS	O(V + E)	O(V)	Graph traversal, tree operations
Dijkstra's Algorithm	O((V + E) log V)	O(V)	Single source shortest path
Union-Find	O(α(n)) amortized	O(n)	Dynamic connectivity, MST
Trie Operations	O(m) where m is key length	O(ALPHABET_SIZE × N × M)	Prefix matching, autocomplete
Segment Tree	O(log n) query/update	O(n)	Range queries with updates

Algorithm/Data Structure

Time Complexity

Space Complexity

Use Cases

Binary Search

O(log n)

O(1)

Sorted arrays, answer-based problems

Merge Sort

O(n log n)

O(n)

Stable sorting, external sorting

Quick Sort

O(n log n) avg, O(n²) worst

O(log n)

In-place sorting, average case performance

Heap Operations

O(log n) insert/delete, O(1) peek

O(n) for heap

Priority queues, top-k problems

Hash Table

O(1) avg, O(n) worst

O(n)

Fast lookups, counting, caching

DFS/BFS

O(V + E)

O(V)

Graph traversal, tree operations

Dijkstra's Algorithm

O((V + E) log V)

O(V)

Single source shortest path

Union-Find

O(α(n)) amortized

O(n)

Dynamic connectivity, MST

Trie Operations

O(m) where m is key length

O(ALPHABET_SIZE × N × M)

Prefix matching, autocomplete

Segment Tree

O(log n) query/update

O(n)

Range queries with updates

🎯 Pattern Selection Guide

📚 For Array/String Problems:

Sliding Window: Subarray/substring problems with contiguous elements
Two Pointers: Sorted arrays, palindromes, or meeting from ends
Prefix Sum: Range sum queries, subarray sum problems
Binary Search: Sorted arrays, answer-based problems

🌳 For Tree/Graph Problems:

DFS: Path problems, tree traversal, backtracking
BFS: Shortest path, level-order traversal, minimum steps
Union-Find: Connectivity problems, dynamic components
Topological Sort: Dependency resolution, course scheduling

⚡ For Optimization Problems:

Dynamic Programming: Overlapping subproblems, optimal substructure
Greedy: Locally optimal choices lead to global optimum
Backtracking: Constraint satisfaction, generate all solutions

🏗️ For Data Structure Design:

Heap: Priority-based operations, top-k problems
Trie: Word/prefix problems, autocomplete
Segment Tree: Range queries with updates
Hash Map: Fast lookups, counting, caching

📝 Study Plan Recommendations

🚀 Beginner Level (Patterns 1-15):

Start with fundamental patterns that appear in 70% of coding interviews. Master these before moving to advanced topics.

🎯 Intermediate Level (Patterns 16-31):

Focus on data structure design and graph algorithms. These patterns are common in system design and complex algorithmic problems.

🏆 Advanced Level (Patterns 32-50):

Specialized algorithms for competitive programming and senior-level interviews. Master these for challenging technical roles.

📈 Practice Strategy:

Solve 3-5 problems per pattern before moving to the next
Focus on pattern recognition rather than memorizing solutions
Time yourself: aim for 20-30 minutes per medium problem
Review and optimize your solutions
Practice explaining your approach out loud