DSA/DSA Patterns.txt at master · code007-1/DSA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
https://leetcode.com/discuss/post/5886397/dsa-patterns-you-need-to-know-by-anubhav-x7og/


https://www.linkedin.com/pulse/20-dsa-patterns-every-software-engineer-should-master-coding-wcqoe/

https://www.youtube.com/channel/UC8tl75PuTYG_nnfO2bGfXxQ


🔑 Core Algorithm Families
Searching & Sorting
Binary Search

Merge Sort

Quick Sort

Heap Sort

Counting Sort

Radix Sort

Graph Algorithms
Breadth First Search (BFS)

Depth First Search (DFS)

Dijkstra’s Algorithm (shortest path)

Bellman-Ford Algorithm

Floyd-Warshall Algorithm

Prim’s Algorithm (minimum spanning tree)

Kruskal’s Algorithm (minimum spanning tree)

Topological Sort

Dynamic Programming
Kadane’s Algorithm (maximum subarray sum)

Longest Common Subsequence

Longest Increasing Subsequence

Matrix Chain Multiplication

Knapsack Problem

Greedy Algorithms
Activity Selection

Huffman Coding

Interval Scheduling

Number Theory & Math
Euclidean Algorithm (GCD)

Sieve of Eratosthenes (prime numbers)

Modular Exponentiation

Chinese Remainder Theorem

String Algorithms
KMP Algorithm (pattern matching)

Rabin-Karp Algorithm

Z Algorithm

Trie-based Searching

Other Essentials
Union-Find / Disjoint Set

Segment Tree

Fenwick Tree (Binary Indexed Tree)

Backtracking Algorithms (N-Queens, Sudoku)

Divide and Conquer


🧩 Less Famous but Interesting Algorithms
Pigeonhole Principle → If you put more items than containers, at least one container has ≥2 items. Used in hashing, birthday paradox, etc.

Dutch National Flag Algorithm → Partitioning arrays into three groups (0s, 1s, 2s). Classic for in‑place sorting with constant space.

Mo’s Algorithm → Offline query processing on arrays using sqrt decomposition. Great for range queries.

Manacher’s Algorithm → Finds longest palindromic substring in linear time.

Boyer–Moore Majority Vote Algorithm → Finds majority element in O(n) time and O(1) space.

Reservoir Sampling → Random sampling from a stream of unknown size.

Tarjan’s Algorithm → Finds strongly connected components (SCCs) in a graph.

Kosaraju’s Algorithm → Another SCC finder using two DFS passes.

Kahn’s Algorithm → Topological sorting using BFS.

Z Algorithm → Efficient string matching, builds Z-array for pattern search.

Rabin–Karp Algorithm → String matching using rolling hash.

Union-Find with Path Compression → Efficient disjoint set operations, used in Kruskal’s MST.

Floyd’s Cycle Detection (Tortoise and Hare) → Detects cycles in linked lists or sequences.

Johnson’s Algorithm → Finds shortest paths between all pairs in sparse graphs.

Knuth Optimization → DP optimization technique for certain cost functions.

Aho–Corasick Algorithm → Multi-pattern string matching using a trie + automaton.

Hopcroft–Karp Algorithm → Finds maximum matching in bipartite graphs.

Edmonds–Karp Algorithm → Implementation of Ford–Fulkerson for max flow using BFS.

KMP Failure Function → Preprocessing step in Knuth–Morris–Pratt string search.

Binary Lifting → Technique for fast LCA (Lowest Common Ancestor) queries in trees.

Heavy-Light Decomposition → Splits a tree into chains for efficient path queries.