Java Competitive Programming Save
I've written some important Algorithms and Data Structures in an efficient way in Java with references to time and space complexity. These Pre-cooked and well-tested codes help to implement larger hackathon problems in lesser time. DFS, BFS, LCA, LCS, Segment Tree, Sparce Table, All Pair Shortest Path, Binary Search, Matching and many more ...
Project README
Java-Competitive-Programming
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.
Algorithms:
| 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 |
Contributions
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
Open Source Agenda is not affiliated with "Java Competitive Programming" Project. README Source: joney000/Java-Competitive-Programming
Stars
102
Open Issues
0
Last Commit
2 months ago
Repository
License
Tags
Algorithms
All Pairs Shortest Path
Bfs
Binary Indexted Tree
Binary Search
Binary Search Tree
Competitive Programming
Consistent Hashing
Dfs
Graph Algorithms
Hashing
Java
Longest Common Subsequence
Lowest Common Ancestor
Matching Algorithm
Maximal Bipartite Matching
Segment Tree
Time Complexity
Two Pointers
Data Structures
Concurrency
Open Source Agenda Badge
