Minimal, clean, and well-documented implementations of data structures and algorithms in Python 3.
Each file is self-contained with docstrings, type hints, and complexity notes — designed to be read and learned from.
pip install algorithmsfrom algorithms.sorting import merge_sort
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]from algorithms.data_structures import BinaryHeap, Trie, BST
from algorithms.graph import dijkstra, bellman_ford
from algorithms.tree import TreeNodeGraph — Dijkstra's shortest path:
from algorithms.graph import dijkstra
graph = {
"s": {"a": 2, "b": 1},
"a": {"s": 3, "b": 4, "c": 8},
"b": {"s": 4, "a": 2, "d": 2},
"c": {"a": 2, "d": 7, "t": 4},
"d": {"b": 1, "c": 11, "t": 5},
"t": {"c": 3, "d": 5},
}
print(dijkstra(graph, "s", "t"))
# (8, ['s', 'b', 'd', 't'])Dynamic programming — coin change:
from algorithms.dynamic_programming import coin_change
# Minimum coins to make amount 29 using denominations [1, 5, 10, 25]
print(coin_change([1, 5, 10, 25], 29))
# 7 (25 + 1 + 1 + 1 + 1)Backtracking — generate permutations:
from algorithms.backtracking import permute
print(permute([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]Data structures — binary heap:
from algorithms.data_structures import BinaryHeap
heap = BinaryHeap()
for val in [5, 3, 8, 1, 9]:
heap.insert(val)
print(heap.remove_min()) # 1
print(heap.remove_min()) # 3Searching — binary search:
from algorithms.searching import binary_search
print(binary_search([1, 3, 5, 7, 9, 11], 7))
# 3 (index of target)Tree — inorder traversal:
from algorithms.tree import TreeNode
from algorithms.tree import inorder
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(inorder(root))
# [1, 2, 3, 4, 6]String — Knuth-Morris-Pratt pattern matching:
from algorithms.string import knuth_morris_pratt
print(knuth_morris_pratt("abxabcabcaby", "abcaby"))
# 6 (starting index of match)python -m pytest tests/algorithms/
data_structures/ # Reusable data structure implementations
array/ # Array manipulation algorithms
backtracking/ # Constraint satisfaction & enumeration
bit_manipulation/ # Bitwise operations & tricks
compression/ # Encoding & compression schemes
dynamic_programming/ # Optimal substructure & memoization
graph/ # Graph algorithms (BFS, DFS, shortest path, flow, ...)
greedy/ # Greedy strategies
heap/ # Heap-based algorithms
linked_list/ # Linked list algorithms
map/ # Hash-map-based algorithms
math/ # Number theory, combinatorics, algebra
matrix/ # 2D array & linear algebra operations
queue/ # Queue-based algorithms
searching/ # Search algorithms (binary, linear, ...)
set/ # Set-based algorithms
sorting/ # Sorting algorithms
stack/ # Stack-based algorithms
streaming/ # Streaming & sketching algorithms
string/ # String matching, manipulation, parsing
tree/ # Tree algorithms (traversal, BST ops, ...)
tests/ # One test file per topic
All core data structures live in algorithms/data_structures/:
| Data Structure | Module | Key Classes |
|---|---|---|
| AVL Tree | avl_tree.py |
AvlTree |
| B-Tree | b_tree.py |
BTree |
| Binary Search Tree | bst.py |
BST |
| Fenwick Tree | fenwick_tree.py |
Fenwick_Tree |
| Graph | graph.py |
Node, DirectedEdge, DirectedGraph |
| Hash Table | hash_table.py |
HashTable, ResizableHashTable |
| Heap | heap.py |
BinaryHeap |
| KD Tree | kd_tree.py |
KDTree |
| Linked List | linked_list.py |
SinglyLinkedListNode, DoublyLinkedListNode |
| Priority Queue | priority_queue.py |
PriorityQueue |
| Queue | queue.py |
ArrayQueue, LinkedListQueue |
| Red-Black Tree | red_black_tree.py |
RBTree |
| Segment Tree | segment_tree.py, iterative_segment_tree.py |
SegmentTree |
| Separate Chaining Hash Table | separate_chaining_hash_table.py |
SeparateChainingHashTable |
| Sqrt Decomposition | sqrt_decomposition.py |
SqrtDecomposition |
| Stack | stack.py |
ArrayStack, LinkedListStack |
| Trie | trie.py |
Trie |
| Union-Find | union_find.py |
Union |
- delete_nth — keep at most N occurrences of each element
- flatten — recursively flatten nested arrays into a single list
- garage — minimum swaps to rearrange a parking lot
- josephus — eliminate every k-th person in a circular arrangement
- limit — filter elements within min/max bounds
- longest_non_repeat — longest substring without repeating characters
- max_ones_index — find the zero to flip for the longest run of ones
- merge_intervals — combine overlapping intervals
- missing_ranges — find gaps between a low and high bound
- move_zeros — move all zeros to the end, preserving order
- n_sum — find all unique n-tuples that sum to a target
- plus_one — add one to a number represented as a digit array
- remove_duplicates — remove duplicate elements preserving order
- rotate — rotate an array right by k positions
- summarize_ranges — summarize consecutive integers as range tuples
- three_sum — find all unique triplets that sum to zero
- top_1 — find the most frequently occurring values
- trimmean — compute mean after trimming extreme values
- two_sum — find two indices whose values sum to a target
- add_operators — insert +, -, * between digits to reach a target
- anagram — check if two strings are anagrams
- array_sum_combinations — find three-element combos from arrays that hit a target sum
- combination_sum — find combinations (with reuse) that sum to a target
- factor_combinations — generate all factor combinations of a number
- find_words — find words on a letter board via trie-based search
- generate_abbreviations — generate all possible abbreviations of a word
- generate_parenthesis — generate all valid parenthesis combinations
- letter_combination — phone keypad digit-to-letter combinations
- palindrome_partitioning — partition a string into palindromic substrings
- pattern_match — match a string to a pattern via bijection mapping
- permute — generate all permutations of distinct elements
- permute_unique — generate unique permutations when duplicates exist
- subsets — generate all subsets (power set)
- minimax — game-tree search with alpha-beta pruning
- subsets_unique — generate unique subsets when duplicates exist
- add_bitwise_operator — add two integers using only bitwise operations
- binary_gap — longest distance between consecutive 1-bits
- bit_operation — get, set, clear, and update individual bits
- bytes_int_conversion — convert between integers and byte sequences
- count_flips_to_convert — count bit flips needed to convert one integer to another
- count_ones — count the number of 1-bits (Hamming weight)
- find_difference — find the added character between two strings using XOR
- find_missing_number — find a missing number in a sequence using XOR
- flip_bit_longest_sequence — longest run of 1s after flipping a single 0
- gray_code — generate Gray code sequences and convert between Gray and binary
- has_alternative_bit — check if binary representation has alternating bits
- insert_bit — insert bits at a specific position in an integer
- power_of_two — check if an integer is a power of two
- remove_bit — remove a bit at a given position
- reverse_bits — reverse all 32 bits of an unsigned integer
- single_number — find the element appearing once (others appear twice) via XOR
- single_number2 — find the element appearing once (others appear three times)
- single_number3 — find two unique elements (others appear twice)
- subsets — generate all subsets using bitmask enumeration
- swap_pair — swap adjacent bit pairs in an integer
- elias — Elias gamma and delta universal integer coding
- huffman_coding — variable-length prefix codes for lossless compression
- rle_compression — run-length encoding for consecutive character compression
- bitmask — travelling salesman problem via bitmask dynamic programming
- buy_sell_stock — maximize profit from a stock price array
- climbing_stairs — count ways to climb stairs taking 1 or 2 steps
- coin_change — minimum coins to make a given amount
- combination_sum — count combinations that sum to a target (with reuse)
- count_paths_dp — count paths in a grid using recursion, memoization, and bottom-up DP
- edit_distance — minimum edits to transform one string into another
- egg_drop — minimize trials to find the critical floor
- fibonacci — compute Fibonacci numbers with memoization
- hosoya_triangle — generate the Hosoya triangle of Fibonacci-like numbers
- house_robber — maximize loot from non-adjacent houses
- int_divide — count the number of integer partitions
- job_scheduling — maximize profit from weighted job scheduling
- k_factor — find the k-factor of a string pattern
- knapsack — maximize value under a weight constraint
- longest_common_subsequence — find the longest common subsequence of two strings
- longest_increasing — find the longest increasing subsequence
- matrix_chain_order — minimize scalar multiplications for matrix chain
- max_product_subarray — find the contiguous subarray with maximum product
- max_subarray — maximum sum subarray (Kadane's algorithm)
- min_cost_path — minimum-cost path through a grid
- num_decodings — count ways to decode a digit string into letters
- planting_trees — optimize tree planting for maximum profit
- regex_matching — match a string against a pattern with
.and*wildcards - rod_cut — maximize revenue from cutting a rod into pieces
- word_break — check if a string can be segmented into dictionary words
- a_star — heuristic shortest-path search (A* algorithm)
- all_factors — find all factor combinations of a number
- all_pairs_shortest_path — Floyd-Warshall all-pairs shortest paths
- bellman_ford — single-source shortest path with negative edge weights
- blossom — Edmonds' blossom algorithm for maximum matching in general graphs
- check_bipartite — determine if a graph is two-colorable
- check_digraph_strongly_connected — check if a directed graph is strongly connected
- clone_graph — deep-copy an undirected graph
- count_connected_number_of_component — count connected components in an undirected graph
- count_islands (BFS) — count islands in a grid using breadth-first search
- count_islands (DFS) — count islands in a grid using depth-first search
- count_islands (Union-Find) — count islands using a disjoint-set structure
- cycle_detection — detect cycles in a directed graph
- dijkstra — single-source shortest path for non-negative weights
- dijkstra_heapq — heap-optimised Dijkstra in O((V+E) log V) for sparse graphs
- find_all_cliques — Bron-Kerbosch algorithm for finding all cliques
- find_path — find paths between two vertices
- kahns_algorithm — topological sort via in-degree counting (Kahn's)
- markov_chain — Markov chain probability modeling
- maximum_flow — compute maximum flow in a flow network
- maximum_flow (BFS) — Edmonds-Karp max-flow (BFS-based Ford-Fulkerson)
- maximum_flow (DFS) — Ford-Fulkerson max-flow via DFS augmenting paths
- maze_search (BFS) — find shortest path through a maze using BFS
- maze_search (DFS) — find a path through a maze using DFS
- minimum_spanning_tree — Kruskal's minimum spanning tree
- pacific_atlantic — find cells that can flow to both oceans
- path_between_two_vertices_in_digraph — check if a path exists in a directed graph
- prims_minimum_spanning — Prim's minimum spanning tree
- satisfiability — 2-SAT satisfiability via implication graph
- shortest_distance_from_all_buildings — find the optimal meeting point in a grid
- strongly_connected_components (Kosaraju) — Kosaraju's SCC algorithm
- sudoku_solver — solve a Sudoku puzzle using constraint backtracking
- tarjan — Tarjan's strongly connected components algorithm
- topological_sort (BFS) — topological ordering using BFS (Kahn's variant)
- topological_sort (DFS) — topological ordering using DFS post-order
- transitive_closure (DFS) — compute the transitive closure of a graph
- traversal — BFS and DFS graph traversal
- walls_and_gates — fill each empty room with distance to nearest gate
- word_ladder — shortest word-to-word transformation sequence
- gale_shapley — stable matching for bipartite preferences (Gale-Shapley)
- max_contiguous_subsequence_sum — maximum contiguous subarray sum (Kadane's algorithm)
- k_closest_points — find k points closest to the origin
- merge_sorted_k_lists — merge k sorted linked lists using a min-heap
- skyline — compute the skyline silhouette from building rectangles
- sliding_window_max — maximum value in each sliding window position
- add_two_numbers — add two numbers stored as reversed linked lists
- copy_random_pointer — deep-copy a linked list with random pointers
- delete_node — delete a node given only a reference to it
- first_cyclic_node — find the first node where a cycle begins (Floyd's)
- intersection — find the intersection point of two singly linked lists
- is_cyclic — detect whether a linked list has a cycle
- is_palindrome — check if a linked list reads the same forwards and backwards
- is_sorted — check if a linked list is sorted in order
- kth_to_last — find the k-th element from the end
- merge_two_list — merge two sorted linked lists into one
- partition — partition a list around a pivot value
- remove_duplicates — remove duplicate values from a linked list
- remove_range — remove nodes within a given index range
- reverse — reverse a linked list iteratively and recursively
- rotate_list — rotate a list right by k positions
- swap_in_pairs — swap every two adjacent nodes
- is_anagram — check if two strings are anagrams via character counting
- is_isomorphic — check if two strings have the same character mapping structure
- longest_common_subsequence — longest common substring using a hash map
- longest_palindromic_subsequence — longest palindromic substring via hash map
- randomized_set — O(1) insert, delete, and get-random data structure
- valid_sudoku — validate a Sudoku board configuration
- word_pattern — check if a string follows a given pattern mapping
- base_conversion — convert integers between arbitrary number bases
- chinese_remainder_theorem — solve a system of modular congruences
- combination — compute binomial coefficients (n choose r)
- cosine_similarity — compute cosine similarity between two vectors
- decimal_to_binary_ip — convert an IP address between decimal and binary
- diffie_hellman_key_exchange — Diffie-Hellman cryptographic key exchange
- distance_between_two_points — Euclidean distance in 2D space
- euler_totient — count integers up to n that are coprime to n
- extended_gcd — extended Euclidean algorithm (GCD with coefficients)
- factorial — compute n! iteratively and recursively
- fft — Fast Fourier Transform (Cooley-Tukey)
- find_order_simple — find the multiplicative order of an element mod n
- find_primitive_root_simple — find a primitive root modulo a prime
- gcd — greatest common divisor and least common multiple
- generate_strobogrammtic — generate strobogrammatic numbers of length n
- goldbach — decompose an even number into a sum of two primes (Goldbach's conjecture)
- hailstone — Collatz conjecture (hailstone) sequence
- is_strobogrammatic — check if a number looks the same upside-down
- krishnamurthy_number — check if a number equals the sum of the factorials of its digits
- linear_regression — ordinary least-squares linear regression with R² and RMSE
- magic_number — check if a number is a magic number
- manhattan_distance — compute Manhattan (L1) distance between two points in any dimension
- modular_exponential — compute (base^exp) mod m efficiently
- modular_inverse — compute the modular multiplicative inverse
- next_bigger — next larger number with the same digits
- next_perfect_square — find the next perfect square after n
- nth_digit — find the n-th digit in the sequence 1, 2, 3, ...
- num_digits — count the number of digits in an integer
- num_perfect_squares — minimum perfect squares that sum to n
- polynomial — polynomial and monomial arithmetic operations
- polynomial_division — polynomial long division returning quotient and remainder
- power — compute x^n via binary exponentiation
- prime_check — check if a number is prime
- primes_sieve_of_eratosthenes — generate primes up to n using the Sieve of Eratosthenes
- pythagoras — Pythagorean theorem calculations
- rabin_miller — Miller-Rabin probabilistic primality test
- recursive_binomial_coefficient — binomial coefficient via Pascal's triangle recursion
- rsa — RSA public-key encryption and decryption
- sqrt_precision_factor — square root to arbitrary precision (Newton's method)
- summing_digits — recursively sum the digits of a number
- surface_area_of_torus — calculate the surface area of a torus
- symmetry_group_cycle_index — cycle index polynomials for symmetry groups
- bomb_enemy — maximize enemies killed by a single bomb placement
- cholesky_matrix_decomposition — Cholesky decomposition of a positive-definite matrix
- copy_transform — copy and transform a matrix
- count_paths — count paths from top-left to bottom-right of a grid
- crout_matrix_decomposition — Crout's LU matrix decomposition
- matrix_exponentiation — raise a matrix to the n-th power efficiently
- matrix_inversion — compute the inverse of a square matrix
- multiply — standard and Strassen matrix multiplication
- rotate_image — rotate an n x n matrix 90 degrees in-place
- search_in_sorted_matrix — search in a row- and column-sorted matrix
- sort_matrix_diagonally — sort each diagonal of a matrix independently
- sparse_dot_vector — dot product of two sparse vectors
- sparse_mul — multiply two sparse matrices efficiently
- spiral_traversal — traverse a matrix in spiral order
- sudoku_validator — validate that a Sudoku board follows all rules
- sum_sub_squares — sum of all k x k sub-squares in a matrix
- max_sliding_window — maximum in each sliding window using a deque
- moving_average — compute a running moving average from a stream
- reconstruct_queue — reconstruct a queue from (height, count) pairs
- zigzagiterator — alternate elements from multiple iterators
- binary_search — search a sorted array in O(log n)
- exponential_search — search a sorted array by doubling the range then binary searching
- find_min_rotate — find the minimum in a rotated sorted array
- first_occurrence — find the first occurrence of a target value
- generalized_binary_search — binary search with a custom predicate
- interpolation_search — search using value-based interpolation
- jump_search — search a sorted array by jumping in fixed blocks
- last_occurrence — find the last occurrence of a target value
- linear_search — sequential scan through an unsorted array
- next_greatest_letter — find the smallest letter greater than a target
- search_insert — find the insertion position for a target value
- search_range — find the first and last positions of a target
- search_rotate — search in a rotated sorted array
- sentinel_search — linear search optimized by placing a sentinel at the end
- ternary_search — search by dividing the array into three parts
- two_sum — find two numbers that sum to a target
- find_keyboard_row — filter words that can be typed on one keyboard row
- randomized_set — O(1) insert, delete, and random-element access
- set_covering — greedy approximation for the set cover problem
- bead_sort — gravity-based natural sorting (bead/abacus sort)
- bitonic_sort — parallel-friendly comparison sort via bitonic sequences
- bogo_sort — random permutation sort (intentionally inefficient)
- bubble_sort — repeatedly swap adjacent out-of-order elements
- bucket_sort — distribute elements into buckets, then sort each
- cocktail_shaker_sort — bidirectional bubble sort
- comb_sort — bubble sort improved with a shrinking gap
- counting_sort — sort integers by counting occurrences
- cycle_sort — in-place sort that minimizes total writes
- exchange_sort — simple pairwise comparison and exchange
- gnome_sort — sort by swapping elements backward until ordered
- heap_sort — sort via a binary heap (in-place, O(n log n))
- insertion_sort — build a sorted portion one element at a time
- meeting_rooms — determine if meeting intervals overlap
- merge_sort — divide-and-conquer stable sort (O(n log n))
- pancake_sort — sort using only prefix reversals
- pigeonhole_sort — sort by placing elements into pigeonhole buckets
- quick_sort — partition-based divide-and-conquer sort
- radix_sort — non-comparative sort processing one digit at a time
- selection_sort — repeatedly select the minimum and swap it forward
- shell_sort — generalized insertion sort with a decreasing gap sequence
- sort_colors — Dutch national flag three-way partition
- stooge_sort — recursive sort by dividing into overlapping thirds
- wiggle_sort — rearrange into an alternating peak-valley pattern
- is_consecutive — check if stack elements are consecutive integers
- is_sorted — check if a stack is sorted in ascending order
- longest_abs_path — find the longest absolute file path in a file system string
- ordered_stack — maintain a stack in sorted order
- remove_min — remove the minimum element from a stack
- simplify_path — simplify a Unix-style file path
- stutter — duplicate each element in a stack
- switch_pairs — swap adjacent pairs of stack elements
- valid_parenthesis — check for balanced parentheses / brackets
- misra_gries — approximate frequent-item detection in a data stream
- one_sparse_recovery — recover a single non-zero element from a stream
- add_binary — add two binary number strings
- alphabet_board_path — navigate a 5×5 alphabet board to spell a target word
- atbash_cipher — Atbash substitution cipher (reverse the alphabet)
- breaking_bad — spell a string using periodic-table element symbols
- caesar_cipher — Caesar shift cipher encryption / decryption
- check_pangram — check if a string contains every letter of the alphabet
- contain_string — find a substring in a string (strStr)
- count_binary_substring — count substrings with equal consecutive 0s and 1s
- decode_string — decode a run-length encoded string like
3[a2[c]] - delete_reoccurring — remove consecutive duplicate characters
- domain_extractor — extract a domain name from a URL
- encode_decode — encode and decode a list of strings
- first_unique_char — find the first non-repeating character
- fizzbuzz — classic FizzBuzz problem
- group_anagrams — group strings that are anagrams of each other
- int_to_roman — convert an integer to a Roman numeral string
- is_palindrome — check if a string reads the same forwards and backwards
- is_rotated — check if one string is a rotation of another
- judge_circle — determine if a sequence of moves returns to the origin
- knuth_morris_pratt — KMP linear-time pattern matching
- license_number — reformat a license key string with dashes
- longest_common_prefix — find the longest common prefix among strings
- longest_palindromic_substring — find the longest palindromic substring
- make_sentence — break a string into valid dictionary words
- manacher — find the longest palindromic substring in O(n) time
- merge_string_checker — check if a string is a valid merge of two others
- min_distance — minimum deletions to make two strings equal
- multiply_strings — multiply two numbers represented as strings
- one_edit_distance — check if two strings are exactly one edit apart
- panagram — find missing letters to complete a pangram
- rabin_karp — Rabin-Karp rolling-hash pattern matching
- repeat_string — minimum string repeats to contain a substring
- repeat_substring — check if a string is built from a repeating pattern
- reverse_string — reverse a string in-place
- reverse_vowel — reverse only the vowels in a string
- reverse_words — reverse the order of words in a string
- roman_to_int — convert a Roman numeral string to an integer
- rotate — rotate a string by k positions
- strip_url_params — remove duplicate query parameters from a URL
- swap_characters — check if one character swap can make two strings equal
- strong_password — check minimum changes needed for a strong password
- text_justification — justify text lines to a specified width
- unique_morse — count unique Morse code representations of words
- validate_coordinates — validate geographic latitude/longitude coordinates
- word_squares — find all valid word squares from a word list
- z_algorithm — Z-array computation for linear-time pattern matching
- bin_tree_to_list — convert a binary tree to a doubly linked list
- binary_tree_paths — enumerate all root-to-leaf paths
- binary_tree_views — left, right, top, and bottom views of a binary tree
- bst_array_to_bst — convert a sorted array into a height-balanced BST
- bst_closest_value — find the value closest to a target in a BST
- bst_count_left_node — count the number of left-child nodes
- bst_delete_node — delete a node from a BST while preserving order
- bst_depth_sum — sum of node values weighted by their depth
- bst_height — calculate the height of a binary tree
- bst_is_bst — validate the binary search tree property
- bst_iterator — lazy in-order iterator for a BST
- bst_kth_smallest — find the k-th smallest element in a BST
- bst_lowest_common_ancestor — lowest common ancestor exploiting BST ordering
- bst_num_empty — count empty (null) branches in a tree
- bst_predecessor — find the in-order predecessor of a BST node
- bst_serialize_deserialize — serialize a BST to a string and back
- bst_successor — find the in-order successor of a BST node
- bst_unique_bst — count structurally unique BSTs for n keys (Catalan number)
- bst_validate_bst — validate a BST using min/max range constraints
- construct_tree_postorder_preorder — reconstruct a tree from pre-order and post-order traversals
- deepest_left — find the deepest left leaf node
- invert_tree — mirror a binary tree (swap all left/right children)
- is_balanced — check if a tree is height-balanced
- is_subtree — check if one tree is a subtree of another
- is_symmetric — check if a tree is a mirror of itself
- longest_consecutive — longest consecutive-value sequence in a tree
- lowest_common_ancestor — find the lowest common ancestor of two nodes
- max_height — maximum depth (height) of a binary tree
- max_path_sum — maximum sum along any path between two nodes
- min_height — minimum depth from root to the nearest leaf
- path_sum — check if any root-to-leaf path sums to a target
- path_sum2 — find all root-to-leaf paths that sum to a target
- pretty_print — pretty-print a binary tree to the console
- same_tree — check if two binary trees are structurally identical
- traversal_inorder — in-order traversal (left, root, right)
- traversal_level_order — level-order (breadth-first) traversal
- traversal_postorder — post-order traversal (left, right, root)
- traversal_preorder — pre-order traversal (root, left, right)
- traversal_zigzag — zigzag (alternating direction) level-order traversal
- trie_add_and_search — trie with wildcard
.search support
Thanks for your interest in contributing! There are many ways to get involved. See CONTRIBUTING.md for details.
Thanks to all the contributors who helped build this repo.