reda2000-cyber / java-competitive-programming

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 in corrections or enhancement? Great! Please raise a PR, or drop a mail at [email protected] .

I also highly recommed to read Introduction to Algorithms(CLRS book) and same algorithm implementation from other authors, it will give you diverse set of ideas to solve same algorithmic challenges.

You can buy me a coffee if you find the implementation helpful. :) https://www.buymeacoffee.com/devjassi