Code Explanations
Greedy
Kruskal’s Minimum Spanning Tree
Constructs a minimum spanning tree by repeatedly adding the shortest edge that does not form a cycle.
Prim’s Minimum Spanning Tree
Grows a minimum spanning tree by starting from a vertex and greedily adding the smallest edge that expands the tree.
Dijkstra’s Shortest Path
Finds the shortest path in a graph with non-negative edge weights by repeatedly choosing the closest unvisited node.
Interval Scheduling Maximization
Selects the maximum number of non-overlapping intervals by always choosing the interval that finishes earliest.
Coin Change (Greedy Variant)
Finds the minimum number of coins for making change, assuming a denomination system where the greedy choice leads to an optimal solution.
Fractional Knapsack
Selects fractions of items to maximize total value given a weight constraint by taking items with the highest value-to-weight ratio first.
Huffman Coding
Builds an optimal prefix-free code for given frequencies by greedily merging the least frequent symbols first.
Job Scheduling (Minimizing Lateness)
Schedules jobs to minimize the maximum lateness by ordering them based on their deadlines.
Best-First Search (Greedy Best-First)
Selects the next path expansion based on an evaluation function (often a heuristic), always expanding the path that appears best at the moment.
Activity Selection Problem
Chooses the maximum number of activities that do not overlap by always picking the next activity that finishes earliest.
Graph
Kruskal’s Algorithm
Builds a minimum spanning tree by sorting edges by weight and adding them if they don’t form a cycle.
Depth-First Search (DFS)
Explores a graph deeply along each branch before backtracking, often implemented using recursion.
Topological Sort
Orders the vertices of a directed acyclic graph so that all directed edges go from earlier in the order to later.
Prim’s Algorithm
Constructs a minimum spanning tree by growing a tree from a starting vertex and adding edges of minimum weight.
Tarjan’s SCC Algorithm
Finds strongly connected components in a directed graph using a depth-first search and a stack-based approach.
Dijkstra’s Algorithm
Finds the shortest path between nodes in a graph with non-negative edge weights.
Johnson’s Algorithm
Computes shortest paths between all pairs of vertices using a combination of reweighting and Dijkstra’s algorithm.
Floyd-Warshall Algorithm
Finds shortest paths between all pairs of vertices in a weighted graph, including those with negative edges (but no negative cycles).
Kosaraju’s SCC Algorithm
Determines strongly connected components by performing multiple DFS passes and leveraging graph transposes.
Bellman-Ford Algorithm
Computes shortest paths from a single source to all other vertices, handles negative edge weights but not negative cycles.
Breadth-First Search (BFS)
Traverses a graph level by level, starting from a root node, exploring all neighbors at one depth before moving to the next.
Maximum Flow (Ford-Fulkerson)
Finds the maximum flow in a network by repeatedly sending flow along augmenting paths until no more can be sent.
Sorting
Heap Sort
Builds a max-heap from the list and repeatedly extracts the maximum element and rebuilds the heap.
Tim Sort
A hybrid stable sorting algorithm derived from merge sort and insertion sort, used in Python’s sort function.
Selection Sort
Selects the minimum element from the unsorted part and swaps it with the element at the beginning of the unsorted part.
Insertion Sort
Inserts each element into its correct position in a growing sorted portion of the array.
Bucket Sort
Divides the input into buckets and sorts each bucket individually, often with another sorting algorithm.
Bubble Sort
Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
Quick Sort
Chooses a pivot, partitions the array into two sides around the pivot, and recursively sorts them.
Counting Sort
Counts the occurrences of each distinct element and places them in the output array in order.
Shell Sort
Starts sorting far-apart elements and progressively reduces the gap between elements to be compared.
Merge Sort
Divides the list into halves, sorts them recursively, and merges the sorted halves.
Radix Sort
Sorts integers digit by digit, starting from the least significant digit to the most significant.
External Sort
Designed to handle data that does not fit into memory and often uses chunking and merging strategies.
Dynamic Programming
Knapsack Problem (0/1)
Maximizes the value of items put into a knapsack without exceeding its capacity by reusing solutions of smaller subproblems.
Matrix Chain Multiplication
Finds the optimal parenthesization of matrix multiplication to minimize the number of scalar multiplications.
Egg Dropping Problem
Determines the minimum number of egg drops needed to find the critical floor using previously computed attempts for fewer eggs or floors.
Partition Problem
Determines if a given set can be partitioned into two subsets of equal sum by building up results from smaller subsets.
Fibonacci Sequence
Computes Fibonacci numbers using overlapping subproblems and caching results to avoid repeated work.
Coin Change
Counts the ways to make change or finds the minimum coins needed by building upon solutions for smaller amounts.
Word Break Problem
Decides if a string can be segmented into dictionary words, using results of subproblems for shorter prefixes.
Longest Common Subsequence (LCS)
Finds the longest subsequence present in both sequences by building solutions to smaller subproblems.
House Robber Problem
Maximizes the amount of money robbed from a line of houses without triggering alarms by not robbing adjacent houses.
Longest Increasing Subsequence (LIS)
Determines the longest strictly increasing subsequence in a sequence using previous computed states.
Rod Cutting Problem
Maximizes revenue by cutting a rod into optimal lengths using known optimal solutions to smaller rod sizes.
Edit Distance (Levenshtein Distance)
Calculates the minimum number of edits (insertions, deletions, substitutions) to transform one string into another.
Tree
Inorder Traversal
Visits left subtree, then node, then right subtree for a systematic linear ordering of a binary tree’s nodes.
Fenwick Tree (Binary Indexed Tree)
Constructs a structure for efficient cumulative frequency or sum queries and updates on an array.
Preorder Traversal
Visits node, then left subtree, then right subtree to record the structure of the tree.
Postorder Traversal
Visits left subtree, then right subtree, then node, often used to delete trees or evaluate expressions.
Segment Tree Construction
Builds a tree-based data structure for range queries (sum, min, max) in O(n) time and space.
Lowest Common Ancestor (LCA) Computation
Finds the lowest common ancestor of two nodes in a tree using preprocessing and queries in O(log n) or better.
Red-Black Tree Insertion
Adds a node to a red-black tree and adjusts colors and rotations to maintain balanced height and ordering.
Binary Search Tree Insertion
Inserts a new key into a BST, maintaining the BST property: left < node < right.
AVL Tree Rotations
Balances an AVL tree by performing rotations (single or double) when subtree heights differ by more than one.
Binary Search Tree Deletion
Removes a key from a BST and rearranges nodes to preserve the BST property.
String
Aho-Corasick
Builds a finite-state machine from a set of patterns to simultaneously search all patterns in O(n + m) time.
Roling Hash (e.g.
Polynomial Rolling Hash)
Suffix Automaton
Builds a minimal deterministic automaton of all suffixes, facilitating fast substring search and analysis.
Manacher’s Algorithm
Finds the longest palindromic substring in linear time by expanding around potential centers.
Suffix Tree Construction (Ukkonen’s Algorithm)
Constructs a compressed trie of all suffixes of a string in O(n) time, enabling fast substring queries.
Suffix Array Construction
Generates a sorted array of all suffixes of a string to enable fast substring searching and comparisons.
LCP Array Construction
Builds an array of longest common prefixes between adjacent suffixes in a suffix array, aiding in string analysis.
Horspool’s Algorithm
A simplified version of Boyer-Moore that uses a single shift table to skip through the text efficiently.
Z-Algorithm
Constructs a Z-array representing the longest substring starting from each position that matches the prefix, enabling efficient pattern search.
Knuth-Morris-Pratt (KMP)
Finds occurrences of a pattern within a string by preprocessing the pattern to skip characters efficiently.
Rabin-Karp
Uses hashing to quickly compare substrings and detect a pattern in a text, allowing average O(n) search.
Boyer-Moore
Searches substrings from right to left, using character skipping rules to often skip large portions of the text.
Hashing
Linear Probing
Resolves collisions by placing the new element in the next available slot in a linear sequence.
Separate Chaining
Handles collisions by maintaining a linked list (chain) of elements sharing the same hash index.
Quadratic Probing
Uses a quadratic function to find the next available slot for a collided key, reducing clustering.
Bloom Filter
A space-efficient probabilistic data structure for testing set membership with false positives but no false negatives.
Cuckoo Hashing
Uses two hash functions and relocates elements until each key is placed in one of its two possible positions.
Hash Table Construction
Builds a data structure mapping keys to values using a hash function to achieve O(1) average lookup time.
Universal Hashing
Chooses a hash function at random from a family of functions to minimize worst-case collision probability.
Double Hashing
Employs two distinct hash functions to find the next free slot on collisions, improving distribution.
Perfect Hashing
Constructs a collision-free hash function that guarantees O(1) lookups for a fixed set of keys.
Rolling Hash
Computes hash values for substrings efficiently, enabling fast string search algorithms like Rabin-Karp.
Searching
Jump Search
Skips ahead by fixed intervals in a sorted list, then performs a linear search within the identified block.
Binary Search
Repeatedly divides a sorted array in half to quickly narrow down the position of the target value.
Linear Search
Sequentially checks each element of the list until the desired element is found or the list is exhausted.
Hash-Based Search
Uses a hash function to directly compute the index of the target, allowing for average O(1) search time.
Best-First Search
Uses an evaluation function to choose which node to explore next, often guided by heuristics.
Exponential Search
First finds a range where the element could be by repeatedly doubling the index, and then applies binary search within that range.
Fibonacci Search
Uses Fibonacci numbers to determine search ranges in a sorted array, similar to binary search but with different mid calculation.
Uniform-Cost Search
Expands the least-cost node first, ensuring the optimal path is found based on cumulative cost.
Breadth-First Search (BFS)
Starts at a root node (or source) and explores all neighbors at the present depth before moving on to the nodes at the next depth level.
A* Search
A graph/tree search algorithm that uses heuristics to find the shortest path to a goal efficiently.
Interpolation Search
Estimates the position of a target in a sorted array using the target’s value and array boundaries, often faster than binary search for uniformly distributed data.
Depth-First Search (DFS)
Explores as far along each branch or path in a graph or tree before backtracking.
Bit Manipulation
Generate Subsets Using Bit Masks
Represents subsets as bit patterns, allowing for quick generation of all subsets of a set.
Reverse Bits of an Integer
Reverses the order of bits in a binary representation of an integer.
Bitwise XOR for Single Element Detection
Utilizes XOR’s properties to find the unique element in an array where every other element appears twice.
Check If Power of Two
Determines if a number is a power of two by checking if it has exactly one set bit.
Extracting and Setting Bits
Uses shifts and masks to isolate, set, or clear specific bits in an integer.
Brian Kernighan’s Algorithm for Counting Set Bits
Counts the number of set bits in an integer by repeatedly stripping away the rightmost set bit.
Compute XOR Prefix/Suffix Arrays
Uses cumulative XOR operations to quickly answer queries about XOR of subarray segments.
Swap Two Variables Using XOR
Interchanges two integer variables without using a temporary variable, relying solely on XOR operations.
BackTrack
Hamiltonian Path Problem
A backtracking approach to determine a path through a graph that visits each vertex exactly once.
Rat in a Maze
A maze-solving algorithm that tries different paths to reach the destination and backtracks when a dead end is encountered.
Cryptarithm Solver
Assign digits to letters in a puzzle and backtrack when inconsistencies arise.
Puzzle Solving
Systematically assign values to variables under constraints, backtracking whenever a conflict occurs.
Combinations Generator
Find all combinations of a given set of items by adding and removing items and backtracking to explore all possibilities.
Graph Coloring
Assign colors to vertices of a graph so that no two adjacent vertices share the same color.
N-Queens Problem
A classic problem where the algorithm tries to place N queens on an N×N chessboard so that no two queens threaten each other.
Permutations Generator
Generate all permutations of a given sequence by swapping and backtracking.
Knight’s Tour
Backtracking method to find a sequence of moves for a knight so it visits every square on a chessboard exactly once.
Sudoku Solver
A backtracking approach to fill a 9x9 grid so that each row, column, and 3x3 subgrid contains all digits from 1 to 9.
Word Search Puzzle Solver
Find a given word in a character grid by exploring possible directions and backtracking when the path does not form the desired word.
Subset Sum
Backtracking to find a subset of numbers that sum up to a given target value.
Divide and Conquer
Quick Sort
Selects a pivot, partitions the array around it, then recursively sorts the subarrays.
Convex Hull (Divide-and-Conquer)
Splits the set of points into subsets, finds their hulls, and merges the hulls to form a global convex hull.
Karatsuba Multiplication
Multiplies two large integers faster than the classical algorithm by recursively splitting and combining results.
Matrix Chain Multiplication (Divide-and-Conquer Variant)
Uses recursive division of the matrix chain to find the optimal multiplication order.
Binary Search
Halves the search interval each time to quickly find an element in a sorted array.
Cooley-Tukey FFT
Computes the Discrete Fourier Transform efficiently by recursively dividing the problem into subproblems.
Closest Pair of Points
Recursively splits the set of points and uses clever combining techniques to find the closest pair in less than O(n²) time.
Strassen’s Matrix Multiplication
Multiplies two matrices faster than the standard algorithm by recursively breaking them down into sub-matrices.
Merge Sort
Divides the array into halves, recursively sorts the halves, and merges the sorted halves.
Median of Medians
Selects a pivot guaranteed to split the array into good portions, ensuring linear time selection.
Linked List
Remove Duplicates
Algorithm for eliminating repeated elements from list
Partition List
Technique for rearranging list elements around a pivot value
Detect Cycle
Method for identifying circular references in linked list
Insertion at Position
Method for adding new node at specific index in linked list
Find Middle Element
Technique for locating center node in linked list
List Traversal
Basic algorithm for sequentially accessing all elements in a linked list
Reverse List
Algorithm for inverting order of linked list elements
Palindrome Check
Method for determining if linked list reads same forward and backward
Merge Sorted Lists
Combining two sorted linked lists into single sorted list
Node Deletion
Technique for removing specific node from linked list
Concurrency
Semaphore Algorithm
Synchronization mechanism controlling access to shared resources through counting mechanism
Deadlock Prevention
Algorithmic techniques for avoiding circular resource waiting in multi-threaded systems
Reader-Writer Lock
Concurrent access control algorithm allowing multiple simultaneous reads but exclusive write access
Parallel Reduction
Efficient parallel computation technique for aggregating data across multiple processing units
Geometry
Point in Polygon
Determining whether a point lies inside or outside a given polygon
Convex Hull
Finding smallest convex polygon enclosing a set of points in a plane
Line Intersection
Detecting and calculating intersection points between multiple line segments
Queue
Double-Ended Queue
Queue allowing insertion and deletion from both ends
Basic Queue Enqueue
Standard method for adding elements to the rear of a queue
Rate Limiting Queue
Queue mechanism for controlling rate of processed elements
Message Queue
Asynchronous communication technique for inter-process messaging
Priority Queue
Queue where elements are served based on priority rather than insertion order
Breadth-First Search
Graph traversal algorithm using queue for level-wise exploration
Round Robin Scheduling
Queue-based algorithm for fair CPU or task scheduling
Circular Queue
Queue implementation using circular array for efficient space utilization
Queue Reversal
Algorithm for reversing order of elements in a queue
Basic Queue Dequeue
Technique for removing and returning the front element from a queue
Mathematical
Gaussian Elimination
A method for solving systems of linear equations and matrix inversion
Linear Programming
A mathematical optimization technique for maximizing or minimizing a linear objective function under linear constraints
Monte Carlo Method
A probabilistic technique for solving problems through repeated random sampling
Graham Scan
An algorithm for computing the convex hull of a set of points in the plane
Convex Hull Algorithm
Determining the smallest convex set that contains all given points in a plane
Newton-Raphson Method
An iterative technique for finding roots of a real-valued function through successive approximations
QuickSort
An efficient divide-and-conquer sorting algorithm that uses partitioning to order elements
Sieve of Eratosthenes
A simple and efficient method for finding all prime numbers up to a given limit
Two Pointers
Sum Pairs
Finding pairs in sorted array that match target sum
Slow-Fast Pointer
Detecting cycles in linked list or array
Reverse String
In-place string reversal using start and end pointers
Merge Sorted Arrays
Combining two sorted arrays efficiently
Three Sum
Locating unique triplets summing to zero in array
Container With Most Water
Finding maximum water container between vertical lines
Sliding Window
Dynamic window technique for array/string subsequence analysis
Remove Duplicates
Efficiently eliminating repeated elements from sorted array
Palindrome Validation
Checking string palindrome using converging pointers
Stack
Depth-First Search
Graph traversal algorithm utilizing stack for node exploration
Basic Stack Push
Standard method for adding elements to the top of a stack
Infix to Postfix Conversion
Stack-based algorithm for converting mathematical expressions
Expression Evaluation
Stack-based method for computing mathematical expressions
Min/Max Stack
Stack variant tracking minimum or maximum element efficiently
Undo Mechanism
Stack implementation for tracking and reversing sequential operations
Balanced Parentheses Check
Using stack to validate matching parentheses in expressions
Recursion Simulation
Using stack to implement recursive algorithm logic
Basic Stack Pop
Technique for removing and returning the top element from a stack
Recursion
Palindrome Checker
Recursively compare characters from the start and end of a string to determine if it reads the same backwards and forwards.
Power Function Implementation
Recursively calculate the power of a number by repeatedly multiplying the base with an decreasing exponent.
Tower of Hanoi
Solve the puzzle of moving a stack of disks from one peg to another with specific rules using recursive strategy.
Factorial Calculation
Calculate the factorial of a number by recursively multiplying the number with factorial of (number - 1).
Directory File Traversal
Recursively explore and list all files and subdirectories within a given directory structure.
Fibonacci Sequence
Compute Fibonacci numbers by recursively calculating the sum of two preceding numbers.
Compression
Huffman Coding
Variable-length encoding algorithm that assigns shorter codes to more frequent symbols
LZW Compression
Dictionary-based algorithm that dynamically builds compression dictionary during encoding
Run-Length Encoding
Simple compression technique that replaces sequences of identical data elements with a single data value and count
Networking
Ethernet CSMA/CD
Media access control method for managing network communication and collision detection
Dijkstra's Routing Algorithm
Dynamic routing protocol for calculating shortest path in computer networks
Nagle's Algorithm
TCP congestion control method for reducing network packet transmission overhead
Reed-Solomon Error Correction
Network error detection and correction algorithm for reliable data transmission
Spanning Tree Protocol
Network algorithm preventing loops in Ethernet networks by creating a loop-free logical topology