Maximum bipartite matching is a common problem on LeetCode and in algorithm interviews. It asks how to pair members of two distinct sets – for example, workers and jobs, or students and projects – so that the number of matched pairs is as large as possible and each element is matched to at most one partner. Understanding this problem improves your grasp of graph algorithms, BFS/DFS techniques, and optimization ideas such as augmenting paths and layering. This topic explains the core concepts, common solution approaches used on LeetCode, implementation tips, and complexity considerations to help you solve and reason about maximum bipartite matching problems effectively.
What is a Bipartite Graph?
A bipartite graph is a graph whose vertices can be split into two disjoint sets, usually called left and right, such that every edge connects a vertex in the left set to a vertex in the right set. No edges exist between vertices within the same set. In the maximum bipartite matching problem, you want to select a set of edges with no shared endpoints that is as large as possible.
Common problem settings on LeetCode
- Matching students to internships given preferences
- Assigning tasks to machines where each machine supports certain tasks
- Allocating resources where each resource can serve one request
- Transforming a grid or matrix problem into bipartite matching (e.g., placing rooks)
LeetCode often hides the graph nature behind a simpler input format (matrices, lists of pairs, or constraints). Part of the skill is translating the input into a bipartite graph representation and choosing the right matching algorithm.
Basic idea augmenting paths
The key insight behind many matching algorithms is the concept of an augmenting path. If you already have a matching, an augmenting path is a path that alternates between edges not in the matching and edges in the matching, starts at a free (unmatched) left vertex and ends at a free right vertex. By flipping the matched/unmatched status of edges along this path, you increase the matching size by one. Repeating this process until no augmenting path exists yields a maximum matching.
How to find augmenting paths
- Depth-First Search (DFS) Start from each free left vertex and try to find a free right vertex through alternating edges. This is straightforward and often works well for smaller inputs.
- Breadth-First Search (BFS) layering Use BFS to build layers of vertices and then DFS within layers to find multiple disjoint augmenting paths of shortest possible length. This is the idea behind Hopcroft-Karp, which makes the algorithm faster on large graphs.
Common algorithms used on LeetCode
There are two algorithms you will see most often for maximum bipartite matching the simple DFS-based augmenting path approach (sometimes called Kuhn’s algorithm) and the Hopcroft-Karp algorithm.
Kuhn’s algorithm (DFS-based)
Kuhn’s algorithm iterates over all vertices on the left side, trying to find an augmenting path using DFS each time. You maintain an array that maps right-side vertices to their matched left partner (or -1 if free). During a DFS from a left vertex, you explore neighbors on the right; if a neighbor is free, you match it; otherwise you recursively try to reassign its current match to another neighbor. Use a visited array per DFS run to avoid cycles.
Advantages
- Simple to implement
- Works well on moderately sized inputs and sparse graphs
Complexity O(V E) in the worst case, though often faster in practice.
Hopcroft-Karp algorithm
Hopcroft-Karp improves performance by finding a maximal set of shortest augmenting paths in each phase. It alternates between a BFS that builds a layered graph and a series of DFS calls that find disjoint augmenting paths constrained by the layering. By augmenting multiple paths per BFS, the algorithm reduces the number of expensive DFS searches.
Advantages
- Asymptotically faster for large graphs
- Worst-case complexity O(sqrt(V) E)
On LeetCode, Hopcroft-Karp is the recommended approach when V and E are large because it scales better.
Implementation tips for LeetCode-style inputs
LeetCode presents problems in various forms. Here are practical tips to convert problem inputs into an adjacency structure and implement matching efficiently
- Use adjacency lists represent the left-side vertex neighbors as lists or vectors for quick traversal.
- Indexing map problem entities to integer indices (0..n-1) for left and right sets to keep arrays small and fast.
- Visited arrays for Kuhn’s algorithm, reset the visited array for every DFS attempt; for Hopcroft-Karp, maintain distance arrays computed in BFS.
- Edge cases handle zero-size left or right sets, and cases where no edges exist.
- Memory keep match arrays of size equal to the number of vertices on each side; initialize with -1.
Practical example structure
A typical flow for solving maximum bipartite matching on LeetCode follows these steps
- Parse input and build adjacency lists for left vertices.
- Choose algorithm use DFS/Kuhn for simpler problems or Hopcroft-Karp for larger inputs.
- Initialize matching arrays leftMatch and rightMatch set to -1.
- Run the chosen algorithm to compute the maximum matching size.
- Return the matching count or construct the actual matched pairs if required by the problem.
Complexity and performance considerations
Choosing between Kuhn and Hopcroft-Karp depends on expected graph size and density. Kuhn’s simplicity makes it a good first attempt and is often enough for typical LeetCode medium problems. If time limits are tight and V and E can be large (for example, thousands of nodes and tens of thousands of edges), Hopcroft-Karp is the safer, performance-oriented choice because its O(sqrt(V) E) bound is much better than Kuhn’s worst case.
Also consider constant factors in your implementation-efficient adjacency structures, iterative instead of recursive approaches if recursion depth is a concern, and avoiding unnecessary data copying will help pass stricter LeetCode tests.
Common pitfalls and debugging tips
- Mixing vertex sets be careful to never treat left and right indices interchangeably-keep separate mapping and match arrays.
- Visited reset forgetting to reset the visited array per attempt causes incorrect results.
- Off-by-one indexing bugs consistent 0-based or 1-based indexing avoids subtle errors.
- Infinite loops ensure BFS/DFS terminate correctly by marking visited and following layering constraints.
- Misinterpreting problem always read whether edges are directed, whether duplicates appear, and if multiple matches per node are allowed (standard matching allows at most one match per vertex).
Wrapping up
Maximum bipartite matching is a foundational topic that appears often on LeetCode and in interviews. Mastering augmenting paths, understanding when to use DFS-based Kuhn versus Hopcroft-Karp, and practicing translation of real problems into bipartite graphs will give you a big advantage. Start by coding a simple DFS solution to build intuition, then implement Hopcroft-Karp to handle larger inputs. With careful attention to indexing, adjacency representation, and edge cases, you’ll be able to solve a wide range of bipartite matching problems and explain your approach clearly in interviews.
2/2