keon/algorithms

algorithms

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.

Quick Start

Install

pip install algorithms

Use

from 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 TreeNode

Examples

Graph — 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 count

# Number of ways to make amount 10 using denominations [2, 5, 3, 6]
print(count([2, 5, 3, 6], 10))
# 5

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())  # 3

Searching — 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)

Run Tests

python -m pytest tests/

Project Structure

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

Data Structures

All core data structures live in algorithms/data_structures/:

Algorithms

Array

• 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

Backtracking

• 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

Bit Manipulation

• 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

Compression

• elias — Elias gamma and delta universal integer coding
• huffman_coding — variable-length prefix codes for lossless compression
• lzw_compression — dictionary-based Lempel-Ziv-Welch compression
• rle_compression — run-length encoding for consecutive character compression

Dynamic Programming

• 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

Graph

• 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

Greedy

• gale_shapley — stable matching for bipartite preferences (Gale-Shapley)
• max_contiguous_subsequence_sum — maximum contiguous subarray sum (Kadane's algorithm)

Heap

• 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

Linked List

• 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

Map

• 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

Math

• 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

Matrix

• 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

Queue

• 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

Searching

• 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

Set

• 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

Sorting

• 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

Stack

• 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

Streaming

• misra_gries — approximate frequent-item detection in a data stream
• one_sparse_recovery — recover a single non-zero element from a stream

String

• 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

Tree

• 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

Contributing

Thanks for your interest in contributing! There are many ways to get involved. See CONTRIBUTING.md for details.

Maintainers

• Keon Kim

Contributors

Thanks to all the contributors who helped build this repo.

License

MIT