Skip to content

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 ...

License

Notifications You must be signed in to change notification settings

joney000/Java-Competitive-Programming

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

About

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 ...

Topics

Resources

License

Stars

Watchers

Forks

Languages