Top Related Projects
All Algorithms implemented in Python
Minimal examples of data structures and algorithms in Python
📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings
120+ interactive Python coding interview challenges (algorithms and data structures). Includes Anki flashcards.
:fireworks:Interactive Online Platform that Visualizes Algorithms from Code
A Python module for learning all major algorithms
Quick Overview
The williamfiset/Algorithms repository is a comprehensive collection of algorithms and data structures implemented in Java. It serves as an educational resource for computer science students and professionals, offering clear implementations and explanations of various algorithmic concepts.
Pros
- Extensive coverage of algorithms and data structures
- Well-documented code with explanations and comments
- Includes unit tests for most implementations
- Regularly updated and maintained
Cons
- Primarily focused on Java implementations
- May lack some advanced or specialized algorithms
- Some implementations might not be optimized for production use
- Limited language support for non-Java developers
Code Examples
- Depth-First Search (DFS) on a graph:
public void dfs(int at) {
visited[at] = true;
for (int next : graph[at]) {
if (!visited[next]) {
dfs(next);
}
}
}
This code performs a depth-first search traversal on a graph, marking visited nodes.
- Binary search on a sorted array:
public static int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
This implementation performs a binary search on a sorted array to find a target value.
- Merge sort algorithm:
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
This code snippet shows the recursive part of the merge sort algorithm, dividing the array and merging sorted subarrays.
Getting Started
To use the algorithms in this repository:
-
Clone the repository:
git clone https://github.com/williamfiset/Algorithms.git
-
Navigate to the desired algorithm's directory.
-
Compile and run the Java file:
javac AlgorithmName.java java AlgorithmName
-
To use in your own project, copy the relevant Java files and import them as needed.
Competitor Comparisons
All Algorithms implemented in Python
Pros of Python
- Larger collection of algorithms and data structures
- Implementations in Python, which is more beginner-friendly
- Active community with frequent contributions
Cons of Python
- Less detailed explanations and comments in the code
- Some implementations may not be optimized for performance
- Lacks the comprehensive test coverage found in Algorithms
Code Comparison
Python (TheAlgorithms/Python):
def binary_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
Java (Algorithms):
public static int binarySearch(int[] arr, int key) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] < key) lo = mid + 1;
else if (arr[mid] > key) hi = mid - 1;
else return mid;
}
return -1;
}
Both repositories offer valuable resources for learning algorithms and data structures. Python provides a broader range of implementations in a more accessible language, while Algorithms offers more detailed explanations and robust testing. The choice between them depends on the user's preferred programming language and learning style.
Minimal examples of data structures and algorithms in Python
Pros of algorithms
- Written in Python, which is more accessible for beginners
- Includes implementations of machine learning algorithms
- Provides interactive Jupyter notebooks for learning
Cons of algorithms
- Less comprehensive coverage of advanced data structures
- Fewer detailed explanations and comments in the code
- Not as actively maintained as Algorithms
Code Comparison
algorithms (Python):
def binary_search(list, item):
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) // 2
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
Algorithms (Java):
public static int binarySearch(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
Both repositories offer valuable algorithm implementations, but they cater to different audiences. algorithms is more suitable for Python enthusiasts and those interested in machine learning, while Algorithms provides a more comprehensive collection of data structures and algorithms with detailed explanations, making it ideal for in-depth study and Java developers.
📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings
Pros of javascript-algorithms
- Focuses specifically on JavaScript implementations, making it ideal for web developers
- Includes explanations and links to further reading for each algorithm
- Offers a wider variety of data structures and algorithms
Cons of javascript-algorithms
- Less comprehensive test coverage compared to Algorithms
- May not be as optimized for performance as the Java implementations in Algorithms
- Lacks some advanced graph algorithms present in Algorithms
Code Comparison
Algorithms (Java):
public static int binarySearch(int[] arr, int key) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (key < arr[mid]) hi = mid - 1;
else if (key > arr[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
javascript-algorithms (JavaScript):
function binarySearch(array, item) {
let start = 0;
let end = array.length - 1;
while (start <= end) {
const middle = Math.floor((start + end) / 2);
if (array[middle] === item) {
return middle;
}
if (item < array[middle]) {
end = middle - 1;
} else {
start = middle + 1;
}
}
return -1;
}
Both repositories offer high-quality implementations of algorithms and data structures. Algorithms provides a more comprehensive collection with a focus on Java, while javascript-algorithms caters specifically to JavaScript developers with additional explanations and resources.
120+ interactive Python coding interview challenges (algorithms and data structures). Includes Anki flashcards.
Pros of interactive-coding-challenges
- Focuses on interactive learning with Jupyter notebooks
- Covers a wide range of topics including data structures, algorithms, and system design
- Includes solutions in multiple programming languages (Python, C++, Java)
Cons of interactive-coding-challenges
- Less comprehensive coverage of advanced algorithms compared to Algorithms
- May not be as suitable for direct implementation in production code
- Updates and maintenance are less frequent
Code Comparison
interactive-coding-challenges (Python):
def reverse_string(string):
if string:
return string[::-1]
return string
Algorithms (Java):
public static String reverse(String s) {
return new StringBuilder(s).reverse().toString();
}
Summary
interactive-coding-challenges offers an interactive learning experience with a broad range of topics and multiple language support. However, it may lack the depth and implementation focus of Algorithms. The code examples show different approaches to string reversal, with interactive-coding-challenges using Python's slicing and Algorithms utilizing Java's StringBuilder.
:fireworks:Interactive Online Platform that Visualizes Algorithms from Code
Pros of Algorithm Visualizer
- Interactive visualization of algorithms, enhancing understanding
- Web-based platform accessible from any device with a browser
- Supports multiple programming languages for algorithm implementation
Cons of Algorithm Visualizer
- Limited to a specific set of algorithms and data structures
- May not be as comprehensive or in-depth as Algorithms
- Focuses more on visualization than code implementation details
Code Comparison
Algorithms (Java):
public static List<Integer> breadthFirstSearch(Map<Integer, List<Integer>> graph, int start) {
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
List<Integer> result = new ArrayList<>();
queue.offer(start);
visited.add(start);
// ... (implementation continues)
}
Algorithm Visualizer (JavaScript):
function bfs(graph, start) {
const queue = [start];
const visited = new Set([start]);
const result = [];
while (queue.length > 0) {
// ... (implementation continues)
}
}
Both repositories offer valuable resources for learning algorithms, but they cater to different needs. Algorithms provides a comprehensive collection of algorithm implementations in various languages, focusing on code and explanations. Algorithm Visualizer, on the other hand, offers an interactive platform for visualizing algorithms, making it easier to understand their behavior but with a more limited scope.
A Python module for learning all major algorithms
Pros of pygorithm
- Focused on Python implementations, making it more accessible for Python developers
- Includes visualization tools for some algorithms, aiding in understanding
- Provides a command-line interface for easy access to algorithm information
Cons of pygorithm
- Smaller collection of algorithms compared to Algorithms
- Less comprehensive documentation and explanations for each algorithm
- Not as actively maintained, with fewer recent updates
Code Comparison
pygorithm (Python):
def binary_search(List, target):
left = 0
right = len(List) - 1
while left <= right:
mid = (left + right) // 2
Algorithms (Java):
public static int binarySearch(int[] ar, int key) {
int lo = 0, hi = ar.length - 1;
while (lo <= hi) {
int mid = lo + ((hi - lo) / 2);
Both implementations show similar approaches to binary search, with pygorithm using Python's more concise syntax and Algorithms using Java's more verbose style. The core logic remains the same in both cases.
Convert designs to code with AI
Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.
Try Visual CopilotREADME
Algorithms & data structures project
Algorithms and data structures are fundamental to efficient code and good software design. Creating and designing excellent algorithms is required for being an exemplary programmer. This repository's goal is to demonstrate how to correctly implement common data structures and algorithms in the simplest and most elegant ways.
Contributing
This repository is contribution friendly :smiley:. If you'd like to add or improve an algorithm, your contribution is welcome! Please be sure to check out the Wiki for instructions.
Other programming languages?
This repository provides algorithm implementations in Java, however, there are other forks that provide implementations in other languages, most notably:
Running an algorithm implementation
To compile and run any of the algorithms here, you need at least JDK version 8. Gradle can make things more convenient for you, but it is not required.
Running with Gradle (recommended)
This project supports the Gradle Wrapper. The Gradle wrapper automatically downloads Gradle the first time it runs, so expect a delay when running the first command below.
If you are on Windows, use gradlew.bat
instead of ./gradlew
below.
Run a single algorithm like this:
./gradlew run -Palgorithm=<algorithm-subpackage>.<algorithm-class>
Alternatively, you can run a single algorithm specifying the full class name
./gradlew run -Pmain=<algorithm-fully-qualified-class-name>
For instance:
./gradlew run -Palgorithm=search.BinarySearch
or
./gradlew run -Pmain=com.williamfiset.algorithms.search.BinarySearch
Compiling and running with only a JDK
Create a classes folder
cd Algorithms
mkdir classes
Compile the algorithm
javac -sourcepath src/main/java -d classes src/main/java/ <relative-path-to-java-source-file>
Run the algorithm
java -cp classes <class-fully-qualified-name>
Example
$ javac -d classes -sourcepath src/main/java src/main/java/com/williamfiset/algorithms/search/BinarySearch.java
$ java -cp classes com.williamfiset.algorithms.search.BinarySearch
Data Structures
- :movie_camera: Balanced Trees
- :movie_camera: Binary Search Tree
- Splay Tree
- :movie_camera: Dynamic Array
- :movie_camera: Fenwick Tree
- Fibonacci Heap
- :movie_camera: Hashtable
- :movie_camera: Linked List
- :movie_camera: Priority Queue
- :movie_camera: Queue
- Segment Tree
- :movie_camera: Sparse Table
- :movie_camera: Stack
- :movie_camera: Suffix Array
- Trie
- :movie_camera: Union Find
Dynamic Programming
Dynamic Programming Classics
- Coin change problem - O(nW)
- Edit distance (iterative) - O(nm)
- Edit distance (recursive) - O(nm)
- :movie_camera: Knapsack 0/1 - O(nW)
- Knapsack unbounded (0/â) - O(nW)
- Maximum contiguous subarray - O(n)
- Longest Common Subsequence (LCS) - O(nm)
- Longest Increasing Subsequence (LIS) - O(n2)
- Longest Palindrome Subsequence (LPS) - O(n2)
- :movie_camera: Traveling Salesman Problem (dynamic programming, iterative) - O(n22n)
- Traveling Salesman Problem (dynamic programming, recursive) - O(n22n)
- Minimum Weight Perfect Matching (iterative, complete graph) - O(n22n)
Dynamic Programming Problem Examples
Adhoc
Tiling problems
- :movie_camera: Tiling Dominoes
- :movie_camera: Tiling Dominoes and Trominoes
- :movie_camera: Mountain Scenes
Geometry
- Angle between 2D vectors - O(1)
- Angle between 3D vectors - O(1)
- Circle-circle intersection point(s) - O(1)
- Circle-line intersection point(s) - O(1)
- Circle-line segment intersection point(s) - O(1)
- Circle-point tangent line(s) - O(1)
- Closest pair of points (line sweeping algorithm) - O(nlog(n))
- Collinear points test (are three 2D points on the same line) - O(1)
- Convex hull (Graham Scan algorithm) - O(nlog(n))
- Convex hull (Monotone chain algorithm) - O(nlog(n))
- Convex polygon area - O(n)
- Convex polygon cut - O(n)
- Convex polygon contains points - O(log(n))
- Coplanar points test (are four 3D points on the same plane) - O(1)
- Line class (handy infinite line class) - O(1)
- Line-circle intersection point(s) - O(1)
- Line segment-circle intersection point(s) - O(1)
- Line segment to general form (ax + by = c) - O(1)
- Line segment-line segment intersection - O(1)
- Longitude-Latitude geographic distance - O(1)
- Point is inside triangle check - O(1)
- Point rotation about point - O(1)
- Triangle area algorithms - O(1)
- [UNTESTED] Circle-circle intersection area - O(1)
- [UNTESTED] Circular segment area - O(1)
Graph theory
Tree algorithms
- :movie_camera: Rooting an undirected tree - O(V+E)
- :movie_camera: Identifying isomorphic trees - O(?)
- :movie_camera: Tree center(s) - O(V+E)
- Tree diameter - O(V+E)
- :movie_camera: Lowest Common Ancestor (LCA, Euler tour) - O(1) queries, O(nlogn) preprocessing
Network flow
- Bipartite graph verification (adjacency list) - O(V+E)
- :movie_camera: Max flow & Min cut (Ford-Fulkerson with DFS, adjacency list) - O(fE)
- Max flow & Min cut (Ford-Fulkerson with DFS, adjacency matrix) - O(fV2)
- :movie_camera: Max flow & Min cut (Edmonds-Karp, adjacency list) - O(VE2)
- :movie_camera: Max flow & Min cut (Capacity scaling, adjacency list) - O(E2log2(U))
- :movie_camera: Max flow & Min cut (Dinic's, adjacency list) - O(EV2) or O(EâV) for bipartite graphs
- Maximum Cardinality Bipartite Matching (augmenting path algorithm, adjacency list) - O(VE)
- Min Cost Max Flow (Bellman-Ford, adjacency list) - O(E2V2)
- Min Cost Max Flow (Johnson's algorithm, adjacency list) - O(E2Vlog(V))
Main graph theory algorithms
- Articulation points/cut vertices (adjacency list) - O(V+E)
- Bellman-Ford (edge list, negative cycles, fast & optimized) - O(VE)
- :movie_camera: Bellman-Ford (adjacency list, negative cycles) - O(VE)
- Bellman-Ford (adjacency matrix, negative cycles) - O(V3)
- :movie_camera: Breadth first search (adjacency list) - O(V+E)
- Breadth first search (adjacency list, fast queue) - O(V+E)
- Bridges/cut edges (adjacency list) - O(V+E)
- Find connected components (adjacency list, union find) - O(Elog(E))
- Find connected components (adjacency list, DFS) - O(V+E)
- Depth first search (adjacency list, iterative) - O(V+E)
- Depth first search (adjacency list, iterative, fast stack) - O(V+E)
- :movie_camera: Depth first search (adjacency list, recursive) - O(V+E)
- :movie_camera: Dijkstra's shortest path (adjacency list, lazy implementation) - O(Elog(V))
- :movie_camera: Dijkstra's shortest path (adjacency list, eager implementation + D-ary heap) - O(ElogE/V(V))
- :movie_camera: Eulerian Path (directed edges) - O(E+V)
- :movie_camera: Floyd Warshall algorithm (adjacency matrix, negative cycle check) - O(V3)
- Graph diameter (adjacency list) - O(VE)
- :movie_camera: Kahn's algorithm (topological sort, adjacency list) - O(E+V)
- Kruskal's min spanning tree algorithm (edge list, union find) - O(Elog(E))
- :movie_camera: Kruskal's min spanning tree algorithm (edge list, union find, lazy sorting) - O(Elog(E))
- Kosaraju's strongly connected components algorithm (adjacency list) - O(V+E)
- :movie_camera: Prim's min spanning tree algorithm (lazy version, adjacency list) - O(Elog(E))
- Prim's min spanning tree algorithm (lazy version, adjacency matrix) - O(V2)
- :movie_camera: Prim's min spanning tree algorithm (eager version, adjacency list) - O(Elog(V))
- Steiner tree (minimum spanning tree generalization) - O(V3 + V2 _ 2T + V _ 3T)
- :movie_camera: Tarjan's strongly connected components algorithm (adjacency list) - O(V+E)
- :movie_camera: Topological sort (acyclic graph, adjacency list) - O(V+E)
- Topological sort (acyclic graph, adjacency matrix) - O(V2)
- Traveling Salesman Problem (brute force) - O(n!)
- :movie_camera: Traveling Salesman Problem (dynamic programming, iterative) - O(n22n)
- Traveling Salesman Problem (dynamic programming, recursive) - O(n22n)
Linear algebra
- Freivald's algorithm (matrix multiplication verification) - O(kn2)
- Gaussian elimination (solve system of linear equations) - O(cr2)
- Gaussian elimination (modular version, prime finite field) - O(cr2)
- Linear recurrence solver (finds nth term in a recurrence relation) - O(m3log(n))
- Matrix determinant (Laplace/cofactor expansion) - O((n+2)!)
- Matrix inverse - O(n3)
- Matrix multiplication - O(n3)
- Matrix power - O(n3log(p))
- Square matrix rotation - O(n2)
Mathematics
- [UNTESTED] Chinese remainder theorem
- Prime number sieve (sieve of Eratosthenes) - O(nlog(log(n)))
- Prime number sieve (sieve of Eratosthenes, compressed) - O(nlog(log(n)))
- Totient function (phi function, relatively prime number count) - O(n1/4)
- Totient function using sieve (phi function, relatively prime number count) - O(nlog(log(n)))
- Extended euclidean algorithm - ~O(log(a + b))
- Greatest Common Divisor (GCD) - ~O(log(a + b))
- Fast Fourier transform (quick polynomial multiplication) - O(nlog(n))
- Fast Fourier transform (quick polynomial multiplication, complex numbers) - O(nlog(n))
- Primality check - O(ân)
- Primality check (Rabin-Miller) - O(k)
- Least Common Multiple (LCM) - ~O(log(a + b))
- Modular inverse - ~O(log(a + b))
- Prime factorization (pollard rho) - O(n1/4)
- Relatively prime check (coprimality check) - ~O(log(a + b))
Other
- Bit manipulations - O(1)
- List permutations - O(n!)
- :movie_camera: Power set (set of all subsets) - O(2n)
- Set combinations - O(n choose r)
- Set combinations with repetition - O((n+r-1) choose r)
- Sliding Window Minimum/Maximum - O(1)
- Square Root Decomposition - O(1) point updates, O(ân) range queries
- Unique set combinations - O(n choose r)
- Lazy Range Adder - O(1) range updates, O(n) to finalize all updates
Search algorithms
- Binary search (real numbers) - O(log(n))
- Interpolation search (discrete discrete) - O(n) or O(log(log(n))) with uniform input
- Ternary search (real numbers) - O(log(n))
- Ternary search (discrete numbers) - O(log(n))
Sorting algorithms
- Bubble sort - O(n2)
- Bucket sort - Î(n + k)
- Counting sort - O(n + k)
- Heapsort - O(nlog(n))
- Insertion sort - O(n2)
- :movie_camera: Mergesort - O(nlog(n))
- Quicksort (in-place, Hoare partitioning) - Î(nlog(n))
- Quicksort3 (Dutch National Flag algorithm) - Î(nlog(n))
- Selection sort - O(n2)
- Radix sort - O(n*w)
String algorithms
- Booth's algorithm (finds lexicographically smallest string rotation) - O(n)
- Knuth-Morris-Pratt algorithm (finds pattern matches in text) - O(n+m)
- Longest Common Prefix (LCP) array - O(nlog(n)) bounded by SA construction, otherwise O(n)
- :movie_camera: Longest Common Substring (LCS) - O(nlog(n)) bounded by SA construction, otherwise O(n)
- :movie_camera: Longest Repeated Substring (LRS) - O(nlog(n))
- Manacher's algorithm (finds all palindromes in text) - O(n)
- Rabin-Karp algorithm (finds pattern match positions in text) - O(n+m)
- Substring verification with suffix array - O(nlog(n)) SA construction and O(mlog(n)) per query
License
This repository is released under the MIT license. In short, this means you are free to use this software in any personal, open-source or commercial projects. Attribution is optional but appreciated.
Donate
Consider donating to support my creation of educational content:
Top Related Projects
All Algorithms implemented in Python
Minimal examples of data structures and algorithms in Python
📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings
120+ interactive Python coding interview challenges (algorithms and data structures). Includes Anki flashcards.
:fireworks:Interactive Online Platform that Visualizes Algorithms from Code
A Python module for learning all major algorithms
Convert designs to code with AI
Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.
Try Visual Copilot