Important Algorithms Summary

How to Use This Reference

Each algorithm gets a single dense paragraph explaining what it does, how it works at a high level, its complexity, and when you would use it. This is your quick-recall reference — if you need depth on any algorithm, read its dedicated article.

Searching Algorithms

Binary Search: On a sorted array, compare the target with the middle element. If target is smaller, search the left half; if larger, search the right half. Each comparison eliminates half the remaining elements, giving O(log n). The most important algorithm to master for interviews — it appears in dozens of problem variants including "binary search on answer" where you search a value space rather than an array.

Depth-First Search (DFS): Explores a graph by going as deep as possible along each branch before backtracking. Uses a stack (explicit or call stack via recursion). O(V + E) time. Used for cycle detection, topological sorting, finding connected components, solving mazes, and generating permutations/combinations via backtracking.

Breadth-First Search (BFS): Explores a graph level by level using a queue. Visits all neighbors of a node before moving to the next level. O(V + E) time. Finds the shortest path in unweighted graphs. Used for level-order tree traversal, finding shortest transformation sequences, multi-source shortest paths, and checking if a graph is bipartite.

Graph Algorithms

Dijkstra's Algorithm: Finds the shortest path from a single source to all other vertices in a weighted graph with non-negative edges. Uses a priority queue to always process the vertex with the smallest known distance. With a binary heap: O((V + E) log V). The greedy choice (process minimum distance vertex) is provably correct for non-negative weights. Does NOT work with negative edges — use Bellman-Ford instead.

Bellman-Ford Algorithm: Finds shortest paths from a single source, handling negative edge weights (unlike Dijkstra). Relaxes all edges V-1 times. O(V × E) time. Can detect negative-weight cycles (if a distance decreases on the Vth iteration, a negative cycle exists). Slower than Dijkstra but more general. Used in network routing (distance-vector protocols).

Floyd-Warshall Algorithm: Computes shortest paths between ALL pairs of vertices simultaneously. Uses dynamic programming with three nested loops — for each intermediate vertex k, update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). O(V³) time, O(V²) space. Simple to implement. Use when you need all-pairs distances and V is small (< 1000).

Kruskal's Algorithm: Finds the Minimum Spanning Tree by sorting all edges by weight and adding them one by one if they do not create a cycle (checked via Union-Find). O(E log E) time dominated by the sort. Efficient for sparse graphs. The greedy choice (always pick lightest edge) provably produces the MST.

Prim's Algorithm: Also finds the MST, but grows a single tree from a starting vertex by always adding the cheapest edge connecting the tree to a non-tree vertex. With a binary heap: O((V + E) log V). Better than Kruskal for dense graphs where E approaches V².

Topological Sort: Orders vertices of a Directed Acyclic Graph (DAG) such that for every edge u→v, u appears before v. Kahn's algorithm (BFS-based): repeatedly remove vertices with in-degree 0. DFS-based: reverse of finish order. O(V + E). Used for build systems, course prerequisites, task scheduling.

Tarjan's Algorithm (SCC): Finds all Strongly Connected Components in a directed graph using a single DFS pass with a stack. Maintains discovery times and low-link values. O(V + E). Used in compiler optimization (reaching definitions), social network analysis, and 2-SAT problems.

Union-Find (Disjoint Set Union): Maintains a collection of disjoint sets supporting union (merge two sets) and find (which set does an element belong to). With union by rank and path compression, nearly O(1) per operation (inverse Ackermann). Used in Kruskal's, connected components, cycle detection, and network connectivity.

Dynamic Programming

Longest Common Subsequence (LCS): Given two strings, find the longest subsequence common to both. Build a 2D table where dp[i][j] = LCS length of first i characters of s1 and first j characters of s2. If characters match, dp[i][j] = dp[i-1][j-1] + 1; otherwise max(dp[i-1][j], dp[i][j-1]). O(m×n) time. Used in diff utilities and bioinformatics.

Edit Distance (Levenshtein): Minimum operations (insert, delete, replace) to transform one string into another. Same 2D DP structure as LCS. dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1] + (0 if match else 1)). O(m×n). Used in spell checkers, DNA sequence alignment, and fuzzy matching.

0/1 Knapsack: Given items with weights and values, and a capacity W, maximize total value without exceeding capacity. dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight_i] + value_i). O(n×W). Space-optimized to O(W) by iterating weights backwards. The quintessential DP problem.

Longest Increasing Subsequence (LIS): Find the longest strictly increasing subsequence. O(n²) with standard DP. O(n log n) with patience sorting: maintain a "tails" array where tails[i] is the smallest tail element of any increasing subsequence of length i+1. Binary search for insertion point.

Matrix Chain Multiplication: Find the optimal way to parenthesize a chain of matrix multiplications to minimize total scalar multiplications. Interval DP: dp[i][j] = min over k of (dp[i][k] + dp[k+1][j] + cost of multiplying results). O(n³). Classic example of interval DP pattern.

Kadane's Algorithm: Find the maximum sum contiguous subarray. Maintain current_sum = max(element, current_sum + element). Track global maximum. O(n) time, O(1) space. Elegant proof: at each position, either start a new subarray or extend the previous one.

String Algorithms

KMP (Knuth-Morris-Pratt): Pattern matching in O(n + m) using a failure function (partial match table) that tells you how far to shift the pattern when a mismatch occurs, avoiding re-examining characters. The failure function is built in O(m) from the pattern alone. Use when you need guaranteed linear-time single-pattern matching.

Rabin-Karp: Uses rolling hash to compare pattern hash with substring hashes. Average O(n + m), worst O(nm) due to hash collisions. The real power is matching multiple patterns simultaneously — compute hashes for all patterns and check in O(1) each. Used in plagiarism detection and multi-pattern search.

Z-Algorithm: Computes the Z-array where Z[i] = length of the longest substring starting at i which is also a prefix of the string. O(n) time. Concatenate pattern + "$" + text, compute Z-array, and positions where Z[i] = pattern length are matches. Simpler to implement than KMP with the same guarantees.

Manacher's Algorithm: Finds all palindromic substrings (specifically, the longest palindromic substring) in O(n) time. Uses previously computed palindrome information to skip redundant comparisons. Tricky to implement but the only truly linear solution for longest palindromic substring.

Mathematical Algorithms

Sieve of Eratosthenes: Finds all primes up to n by iteratively marking multiples of each prime starting from 2. O(n log log n) time. The most efficient way to generate all primes below a bound. Start marking from p² (all smaller multiples already marked by smaller primes).

Fast Exponentiation (Binary Exponentiation): Computes a^n in O(log n) by squaring: if n is even, a^n = (a^(n/2))². If odd, a^n = a × a^(n-1). Used for modular exponentiation in cryptography and competitive programming. Extends to matrix exponentiation for computing Fibonacci in O(log n).

Euclidean Algorithm (GCD): Computes greatest common divisor using gcd(a, b) = gcd(b, a mod b) with base case gcd(a, 0) = a. O(log(min(a,b))) iterations. Extended Euclidean additionally finds x, y such that ax + by = gcd(a,b). Foundation for modular inverse and RSA cryptography.

Modular Arithmetic: Key operations: (a + b) mod m = ((a mod m) + (b mod m)) mod m. Same for multiplication. Division requires modular inverse (a^(m-2) mod m when m is prime, by Fermat's little theorem). Essential in competitive programming to prevent overflow with answers "modulo 10^9 + 7."