Watch 9 video solutions for Minimum Cost to Connect Two Groups of Points, a hard level problem involving Array, Dynamic Programming, Bit Manipulation. This walkthrough by Hua Hua has 2,030 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 100Problem 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 | 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 |