Minimum Cost to Connect Two Groups of Points: Bitmask DP
You are given two groups of points and a cost matrix. cost[i][j] is the cost to connect the i-th point in group1 to the j-th point in group2. Every point in both groups must be connected to at least one point in the other group. Find the minimum total cost to achieve this.
This is LeetCode 1595: Minimum Cost to Connect Two Groups of Points, a hard problem that combines bitmask DP with a bipartite graph structure. The constraint that every point on both sides must be connected makes this trickier than a standard assignment problem. You cannot just greedily pick cheap edges, because skipping a group2 point means you will have to pay for it later.
Why this problem matters
This problem is a clean example of how bitmask DP handles "coverage" constraints. In many real-world scenarios (task assignment, network design, resource allocation), you need to ensure that every element on one side is served by at least one element on the other side. The bitmask lets you track exactly which elements have been covered, turning an exponential search into polynomial-time DP.
If you have worked through problems like Partition Equal Subset Sum or Coin Change, you already understand how DP collapses overlapping subproblems. This problem adds a new dimension: the bitmask. Once you are comfortable encoding set coverage as bits, you unlock a whole family of hard DP problems.
The key insight
Think of this as a two-phase process:
- Phase 1: Iterate through each group1 point and connect it to at least one group2 point. Track which group2 points have been covered so far using a bitmask.
- Phase 2: After all group1 points have been assigned, check if any group2 points are still uncovered. If so, connect each uncovered point to whichever group1 point gives the cheapest cost.
The bitmask mask is an integer where bit j is set to 1 if group2 point j has been connected. For n group2 points, mask ranges from 0 to (1 << n) - 1. The state dp[i][mask] means: "the minimum cost after assigning the first i group1 points, with group2 coverage described by mask."
For the second phase, you precompute min_cost[j] = the cheapest edge connecting any group1 point to group2 point j. After processing all group1 points, if bit j is not set in the mask, you add min_cost[j] to the total. This guarantees full coverage on both sides.
The solution
def connectTwoGroups(cost):
m, n = len(cost), len(cost[0])
min_cost = [min(cost[i][j] for i in range(m)) for j in range(n)]
full = (1 << n) - 1
INF = float('inf')
dp = [[INF] * (full + 1) for _ in range(m + 1)]
dp[0][0] = 0
for i in range(m):
for mask in range(full + 1):
if dp[i][mask] == INF:
continue
for j in range(n):
new_mask = mask | (1 << j)
val = dp[i][mask] + cost[i][j]
if val < dp[i][new_mask]:
dp[i][new_mask] = val
if val < dp[i + 1][new_mask]:
dp[i + 1][new_mask] = val
ans = INF
for mask in range(full + 1):
if dp[m][mask] == INF:
continue
total = dp[m][mask]
for j in range(n):
if not (mask & (1 << j)):
total += min_cost[j]
if total < ans:
ans = total
return ans
Here is what each section of the code does.
Precompute minimum costs: For each group2 point j, min_cost[j] stores the cheapest connection from any group1 point. This will be used in the final step to handle uncovered group2 points.
Initialize the DP table: dp[i][mask] starts at infinity for all states except dp[0][0] = 0, which represents the starting state where no group1 points have been processed and no group2 points are covered.
Fill the DP table: For each group1 point i and each coverage state mask, try connecting i to every group2 point j. This updates two states:
dp[i][new_mask]: connect another edge from the same group1 pointi(a group1 point can connect to multiple group2 points).dp[i+1][new_mask]: move on to the next group1 point after this connection.
Collect the answer: After processing all m group1 points, check each mask. For any group2 point j not covered by mask, add min_cost[j]. The minimum across all masks is the answer.
The transition dp[i][new_mask] = min(dp[i][new_mask], dp[i][mask] + cost[i][j]) is what allows a single group1 point to connect to multiple group2 points. Without it, you could only assign each group1 point to exactly one group2 point, which would miss the optimal solution in many cases.
Visual walkthrough
Step 1: Precompute the minimum connection cost for each group2 point
For each column j, find min(cost[i][j]) over all rows i. These values are used later to cheaply cover any group2 point left unconnected.
Step 2: Define dp[i][mask] where mask tracks which group2 points are connected
i ranges over group1 points (0 to m). mask is a bitmask of size n (group2 size). dp[i][mask] = minimum cost after assigning the first i group1 points, with group2 coverage given by mask.
Step 3: For each group1 point i, try connecting it to every group2 point j
Transition: dp[i+1][mask | (1 << j)] = min(dp[i+1][mask | (1 << j)], dp[i][mask] + cost[i][j]). Each group1 point must connect to at least one group2 point, so we try all j.
Step 4: After all group1 points assigned, cover any remaining group2 points
If mask != (1 << n) - 1 after processing all group1 points, some group2 points are uncovered. Add the precomputed minimum cost for each missing group2 point.
Step 5: The answer is dp[m][(1 << n) - 1], the state with all group2 points covered
For cost = [[1,3,5],[4,1,1],[1,5,3]], the answer is dp[3][111] = 4. Optimal connections: A0-B0(1), A1-B1(1), A1-B2(1), A2-B0(1).
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Brute force (try all subsets of edges) | O(2^(m*n)) | O(m * n) |
| Bitmask DP | O(m * n * 2^n) | O(m * 2^n) |
Time: O(m * n * 2^n). For each of the m group1 points, you iterate over all 2^n masks and try n group2 connections. The constraint n <= 12 means 2^12 = 4096, so this runs comfortably within limits.
Space: O(m * 2^n) for the DP table. With m up to 12 and 2^n up to 4096, that is about 50,000 entries.
The building blocks
1. Bitmask DP for set coverage
The core technique here is encoding "which elements are covered" as a bitmask. This pattern appears whenever you need to track a subset of items and the total number of items is small (typically <= 20). The bitmask turns subset operations into fast bitwise operations: union is |, membership check is &, and complement is ^. You see this same structure in problems like Travelling Salesman (track visited cities), Shortest Superstring (track included strings), and Parallel Courses II (track completed prerequisites).
2. Two-phase assignment with greedy cleanup
The idea of assigning group1 points first and then greedily covering leftover group2 points is a powerful decomposition. By precomputing the minimum cost for each group2 point, the cleanup phase is O(n) per mask. This "assign then fix" pattern shows up in many covering and assignment problems where one side has a natural ordering (here, group1 points) and the other side has a coverage constraint (here, all group2 points must be connected).
Edge cases
- Single point in each group: the answer is simply
cost[0][0]. The only possible connection is the one available edge. - One group1 point, multiple group2 points: group1 point 0 must connect to every group2 point (since every group2 point needs at least one connection, and there is only one group1 point). The cost is the sum of all
cost[0][j]. - All costs are equal: any valid connection set works, and the answer equals the number of edges in a minimum valid connection. That minimum is
max(m, n)edges. - Cost matrix has zeros: zero-cost edges are always worth taking. They effectively "free" the coverage of a group2 point.
- m or n equals 1: when one group has a single point, that point must connect to all points in the other group. The problem reduces to a simple sum.
From understanding to recall
You now understand how bitmask DP tracks group2 coverage, how the two-phase approach ensures full coverage on both sides, and why precomputing minimum costs for group2 makes the cleanup step efficient. But knowing the approach is different from writing it under pressure.
In an interview, you need to set up the bitmask, define the state as dp[i][mask], write the double update transition (same row and next row), and handle the final cleanup loop. The bitmask DP pattern is one of roughly 60 reusable building blocks in the CodeBricks system. Drilling it with spaced repetition until the bitmask setup, transition logic, and cleanup step are automatic is how you go from "I get it" to "I can code it cold in 15 minutes."
Related posts
- Partition Equal Subset Sum - A simpler DP that also tracks subset properties (achievable sums instead of coverage masks). Great for building DP intuition before tackling bitmask problems.
- Edit Distance - Classic 2D DP on two sequences. Same flavor of "process one dimension row by row" that appears in this problem's group1 iteration.
- Coin Change - Unbounded knapsack DP that introduces the idea of trying all options at each step. The same "try every group2 point for each group1 point" logic appears here.
CodeBricks breaks problems like this into reusable building blocks and drills them with spaced repetition so you can write the solution from memory when it counts.