In This Repository, I have written some of the important Algorithms and Data Structures efficiently in Java with proper references to time and space complexity. These Pre-cooked and well-tested codes helps to implement larger hackathon problems in lesser time.
| Algorithm | Big-O Time, Big-O Space | Comments/Symbols |
|---|---|---|
| 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) |
| Multiset | O(log(N)), O(N) | N = no of objects in the multiset. get/add: O(log n) and Average Case O(1) |
| MillerRabin | O(log(N)), O(1) | deterministic algorithm to identify if a number is prime or not |
| Disjoint Set Union - DSU | O(log(N)), O(N) | merge disjoint sets with O(log n) merge operation with path optimization |
Want to contribute to corrections or enhancement or any new idea around algorithms? Great! Please raise a PR, or drop a mail at [email protected] .
I also highly recommend reading Introduction to Algorithms(CLRS book) and same algorithm implementation from other authors, it will give you a diverse set of ideas to solve the same algorithmic challenge.
You can buy me a coffee if you find the implementation helpful. :) https://www.buymeacoffee.com/devjassi