| DFS - 2-D Grid |
O(M * N), O(M * N) |
M * N = dimensions of matrix |
| DFS - Adjency List |
O(V + E), O(V + E) |
V = No of vertices in Graph, E = No of edges in Graph |
| BFS - 2-D Grid |
O(M * N), O(M * N) |
M * N = dimensions of matrix |
| BFS - Adjency List |
O(V + E), O(V + E) |
V = No of vertices in Graph, E = No of edges in Graph |
| LCA - Lowest Common Ancestor |
O(V), O(V) |
|
| LCA - Using Seg Tree |
O(log V), O(V + E) |
Using Euler tour and Segment Tree, preprocessing/building tree = O(N) & Each Query = O(log N) |
| All Pair Shortest Path |
O(V^3), O(V + E) |
Floyd Warshall algorithm |
| Longest Common Subsequence |
O(M * N), O(M * N) |
Finding LCS of N & M length string using Dynamic Programming |
| Binary Search |
O(log(N), O(N) |
Search in N size sorted array |
| Lower Bound Search |
O(log(N), O(1) |
Unlike C, Java Doesn't Provide Lower Bound, Upper Bound for already sorted elements in the Collections |
| Upper Bound Search |
O(log(N), O(1) |
|
| Maximal Matching |
O(√V x E), O(V + E) |
Maximum matching for bipartite graph using Hopcroft-Karp algorithm |
| Minimum Cost Maximal Matching - Hungarian algorithm |
O(N^3), O(N^2) |
|
| Matrix Exponentiation |
O(N^3 * log(X)) ,O(M * N) |
Exponentiation by squaring / divide and conquer MATRIX[N, N] ^ X |
| Segment Tree |
O(Q * log(N)), O(N) |
Q = no of queries , N = no of nodes , per query time = O(log N) |
| Segment Tree Lazy Propagation |
O(Q * log(N)), O(N) |
Q = no of queries , N = no of nodes , tree construction time = O(N), per query time = O(log N), range update time: O(log N) |
| Sparse Table |
O(Q * O(1) + N * log(N)), O(N * log(N)) |
per query time = O(1) and precompute time and space: O(N * log(N)) |
| Merge Sort |
O(N * log(N)), O(N) |
divide and conquer algorithm |
| Miller Prime Test |
soft-O notation Õ((log n)^4) with constant space |
|
| Kruskal- Minimum Spanning Tree |
O(E log V) , O(V + E) |
|
| BIT - Binary Index Tree / Fenwick Tree |
O(log N), O(N) |
per query time: O(log(N)) |
| Two Pointers |
O(N), O(N) |
two directional scan on sorted array |
| Binary Search Tree - BST |
O(N), O(N) |
|
| Maximum Subarray Sum |
O(N), O(N) |
Kadane's algorithm |
| Immutable Data Structures, Persistent Data Structurs - Persistent Trie |
O(N * log N), O(N) |
query & update time: O(log N). It's frequently used where you have to maintain multiple version of your data structure typically in lograthimic time. |
| Dijkstra |
O((E+v) log V)), O(V + E) |
|
| Z - Function |
O(P + T), O(P + T) |
Leaner time string matching / occurrence finding of pattern string P into Large Text string T. |
| Heavy Light Decomposition |
O(N * log^2 N), O(N) |
per query time = (log N)^2 |
| Interval Merge |
O(log N), O(N) |
|
| Knapsack |
O(N * S), (N * S) |
N = elements, S = MAX_Sum |
| Suffix Array and LCP - Longest Common Prefix |
O(N * log(N)), O(N) |
|
| Squre Root Decomposition |
O(N * √N), O(N) |
the range of N number can be divided in √N blocks |
| Kth Order Statics |
O(N), O(N) |
K’th Smallest/Largest Element in Unsorted Array |
| Trie / Prefix Tree |
O(N * L), O(N * L) |
if there are N strings of L size, per query time(Prefix information) = O(L) |
| LIS - Longest Increasing Subsequence |
O(N * log(N)), O(N) |
|
| Priority Queue |
O(log(N)), O(N) |
N = no of objects in the queue. peek: O(1), poll/add: O(log n) |