Minimum Cost to Connect Two Groups of Points - Solution & Explanation
Problem Statement
You are given two groups of points where the first group has size1 points, the second group has size2 points, and size1 >= size2.
The cost of the connection between any two points are given in an size1 x size2 matrix where cost[i][j] is the cost of connecting point i of the first group and point j of the second group. The groups are connected if each point in both groups is connected to one or more points in the opposite group. In other words, each point in the first group must be connected to at least one point in the second group, and each point in the second group must be connected to at least one point in the first group.
Return the minimum cost it takes to connect the two groups.
Example 1:
Input: cost = [[15, 96], [36, 2]] Output: 17 Explanation: The optimal way of connecting the groups is: 1--A 2--B This results in a total cost of 17.
Example 2:
Input: cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]] Output: 4 Explanation: The optimal way of connecting the groups is: 1--A 2--B 2--C 3--A This results in a total cost of 4. Note that there are multiple points connected to point 2 in the first group and point A in the second group. This does not matter as there is no limit to the number of points that can be connected. We only care about the minimum total cost.
Example 3:
Input: cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]] Output: 10
Constraints:
size1 == cost.lengthsize2 == cost[i].length1 <= size1, size2 <= 12size1 >= size20 <= cost[i][j] <= 100
Approach Overview
Problem Overview: You are given a cost matrix where cost[i][j] represents the cost of connecting point i from group 1 to point j from group 2. Every point in both groups must be connected to at least one point in the opposite group. The goal is to minimize the total connection cost.
Approach 1: Recursive Backtracking with Caching (O(m * n * 2^n) time, O(m * 2^n) space)
This approach explores all ways to connect points from group 1 to group 2 using recursion. At each step, you choose a connection between the current point in group 1 and any point in group 2, tracking which group‑2 points are already connected using a bitmask. Memoization caches results for states defined by (index, mask) to avoid recomputation. After processing all group‑1 points, any group‑2 point not yet connected is attached using its minimum possible cost. This reduces the exponential search space significantly and works well within the constraints.
Approach 2: Dynamic Programming with Bitmask (O(m * n * 2^n) time, O(2^n) space)
This is the optimized solution typically expected in interviews. Use a DP state where dp[mask] represents the minimum cost after connecting some points in group 1 such that the set of connected points in group 2 equals mask. Iterate through each point in group 1 and update the DP by trying connections to every point in group 2. Bit operations track which points are already connected. Precompute the minimum cost for connecting each group‑2 point so that any remaining unconnected points can be handled at the end. The key insight is representing connection states compactly with a bitmask and progressively building optimal solutions.
The DP formulation relies heavily on dynamic programming and bitmask techniques to compress state space. The input itself is modeled as a matrix, where each entry represents a possible connection cost.
Recommended for interviews: Dynamic Programming with Bitmask is the expected solution. It demonstrates strong state modeling and efficient subset processing. The recursive solution with caching is easier to reason about initially and helps verify correctness, but the iterative DP version shows stronger control over state transitions and space optimization.
Approach 1: Dynamic Programming with Mask
This approach uses a dynamic programming strategy, specifically leveraging a mask to represent which points in the second group have been connected. The state in our DP table will keep track of the minimal cost to connect a certain number of points from the first group to the desired points in the second group. The largest runtime occurs when we compute the transition costs, but overall the approach is feasible due to small group sizes.
The algorithm initializes a dynamic programming table where dp[i][mask] represents the minimum cost to connect the first i points in group one with a set mask of group two points. We iterate over all possible states and transitions, updating our DP table with the minimum possible costs. Finally, we account for any points in group two not included in the final mask, adding the minimum possible connection cost from any group one point.
Complexity
Time Complexity: O(size1 * size2 * 2^size2)
Here, we iterate through group one and use binary masks to represent the subset of group two. Transitions cost O(size2) for each mask.
Space Complexity: O(size1 * 2^size2)
We need a DP table of size proportionate to state (point and mask).
Approach 2: Recursive Backtracking with Caching
This method employs recursive backtracking to explore every possible way of connecting points from the first group to the second group. Caching intermediate results helps prevent redundant computations, suitable for this problem size, allowing the recursion to operate within feasible limits.
The recursive method in this C program deduplicates potential paths via a recursive DFS function. Marked progress is cached, ensuring each step updates a mask of reached nodes. This reduces computations over large states.
Complexity
Time Complexity: O(size1 * size2 * 2^size2)
Considers recursive calls with full branching over size2 subset options.
Space Complexity: O(size1 * 2^size2)
Space consumed for caching possible state solutions increases with problem constraints.
Approach 3: Bitmask Dynamic Programming
Let m and n denote the number of points in the first group and the second group, respectively.
Since 1 leq n leq m leq 12, we can use an integer to represent the state of points in the second group — specifically, a binary integer of length n, where bit k being 1 means the k-th point in the second group is connected to some point in the first group, and 0 means it is not.
Next, we define f[i][j] as the minimum cost when the first i points in the first group are all connected, and the state of points in the second group is j. Initially, f[0][0] = 0 and all other values are positive infinity. The answer is f[m][2^n - 1].
Consider f[i][j] where i geq 1. We enumerate each point k in the second group. If point k is connected to the i-th point in the first group, we discuss the following two cases:
- If point
kis only connected to thei-th point in the first group, thenf[i][j]can be transitioned fromf[i][j \oplus 2^k]orf[i - 1][j \oplus 2^k], where\oplusdenotes the XOR operation; - If point
kis connected to thei-th point in the first group as well as other points, thenf[i][j]can be transitioned fromf[i - 1][j].
In both cases, we take the minimum transition value:
$
f[i][j] = min_{k \in {0, 1, cdots, n - 1}} {f[i][j \oplus 2^k], f[i - 1][j \oplus 2^k], f[i - 1][j]} + cost[i - 1][k]
Finally, we return f[m][2^n - 1].
The time complexity is O(m times n times 2^n) and the space complexity is O(m times 2^n), where m and n$ are the number of points in the first group and the second group, respectively.
Approach 4: Bitmask Dynamic Programming (Space Optimization)
We notice that the transition of f[i][j] only depends on f[i - 1][cdot] and f[i][cdot], so we can use a rolling array to optimize the space complexity down to O(2^n).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Mask | Time Complexity: O(size1 * size2 * 2^size2) |
| Recursive Backtracking with Caching | Time Complexity: O(size1 * size2 * 2^size2) |
| Bitmask Dynamic Programming | — |
| Bitmask Dynamic Programming (Space Optimization) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking with Caching | O(m * n * 2^n) | O(m * 2^n) | Good for understanding the state transitions and building intuition before optimizing |
| Dynamic Programming with Bitmask | O(m * n * 2^n) | O(2^n) | Best general solution for constraints up to 12 points per group |
Video Solution
花花酱 LeetCode 1595. Minimum Cost to Connect Two Groups of Points - 刷题找工作 EP358 • Hua Hua • 2,038 views views
Watch 8 more video solutions →Frequently Asked Questions
Is Minimum Cost to Connect Two Groups of Points easy or hard?
Minimum Cost to Connect Two Groups of Points Python/Java solution
What is the best approach for Minimum Cost to Connect Two Groups of Points?
How to solve Minimum Cost to Connect Two Groups of Points in O(m * n * 2^n)?
Is Minimum Cost to Connect Two Groups of Points asked at Google/Amazon/Meta?
What data structure is used in Minimum Cost to Connect Two Groups of Points?
What is the time complexity of Minimum Cost to Connect Two Groups of Points?
Ready to solve this problem?
Practice Minimum Cost to Connect Two Groups of Points with our built-in code editor and test cases.
Practice on FleetCode