#1595

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Cost to Connect Two Groups of Points

Compute the minimum cost to fully connect two groups of points using dynamic programming and bitmasking efficiently.

array dynamic programming bit manipulation matrix bitmask

Problem Statement

You are given two groups of points: the first group contains size1 points and the second group contains size2 points, where size1 >= size2. 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.

A cost matrix of size1 x size2 is provided, where cost[i][j] represents the cost to connect point i from the first group with point j from the second group. Compute and return the minimum total cost required to establish connections such that every point in both groups is connected to at least one point in the opposite group.

Examples

Example 1

Input: cost = [[15, 96], [36, 2]]

Output: 17

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

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

Example details omitted.

Constraints

size1 == cost.length
size2 == cost[i].length
1 <= size1, size2 <= 12
size1 >= size2
0 <= cost[i][j] <= 100

Solution Approach

Dynamic Programming with Bitmasking

Use a DP table where dp[i][mask] represents the minimum cost to connect the first i points of the first group to any subset of points in the second group represented by mask. Iterate through all points in the first group, updating dp entries by considering connecting the current point to every point in the second group, combining previous masks using bitwise OR operations.

Iterate Over Subsets Efficiently

Since each second-group point must be connected at least once, iterate over all subsets of connections using bit manipulation. For each DP state, consider adding connections from the current first-group point to unconnected second-group points, updating the DP state only if it improves the current minimum cost.

Final State and Result Extraction

After processing all first-group points, the minimum total cost is the value in dp[size1][full_mask], where full_mask has all second-group points connected. This ensures every second-group point is covered, and the DP table has aggregated the minimal cost across all valid connection combinations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(size1 * 2^size2 * size2), as we process each first-group point and all subsets of second-group points. Space complexity is O(2^size2) if optimizing with a rolling DP array, otherwise O(size1 * 2^size2) for a full DP table.

What Interviewers Usually Probe

Expecting knowledge of state transition DP with bitmask representation
Looking for correct handling of subsets and connection coverage
Watch for optimization by reducing unnecessary DP updates

Common Pitfalls or Variants

Common pitfalls

Forgetting that each second-group point must be connected at least once
Incorrectly updating DP without considering previous masks
Overlooking that multiple first-group points can connect to the same second-group point without extra cost

Follow-up variants

Connection cost matrix may be asymmetric or contain zeros
Number of points in groups can be equal or have first group larger
Cost limits can vary, requiring careful handling of maximum sums

FAQ

What is the main challenge in Minimum Cost to Connect Two Groups of Points?

The key challenge is ensuring each point in both groups is connected at least once while minimizing total cost, using state transition DP.

How does bitmasking help in this problem?

Bitmasking allows efficient representation of subsets of second-group points already connected, enabling quick DP state transitions and cost updates.

Can multiple first-group points connect to the same second-group point?

Yes, multiple first-group points can connect to the same second-group point without additional restrictions; the goal is minimal total cost.

What is the time complexity of the DP approach?

The time complexity is O(size1 * 2^size2 * size2) because for each first-group point we iterate over all subsets of second-group points and all possible connections.

Is this problem always solvable for size1 >= size2?

Yes, as long as size1 >= size2, a solution exists since DP can always assign connections to cover all points efficiently.

terminal

Solution

Solution 1: Bitmask Dynamic Programming

Let $m$ and $n$ denote the number of points in the first group and the second group, respectively.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def connectTwoGroups(self, cost: List[List[int]]) -> int:
        m, n = len(cost), len(cost[0])
        f = [[inf] * (1 << n) for _ in range(m + 1)]
        f[0][0] = 0
        for i in range(1, m + 1):
            for j in range(1 << n):
                for k in range(n):
                    if (j >> k & 1) == 0:
                        continue
                    c = cost[i - 1][k]
                    x = min(f[i][j ^ (1 << k)], f[i - 1][j], f[i - 1][j ^ (1 << k)]) + c
                    f[i][j] = min(f[i][j], x)
        return f[m][-1]

Solution 2: 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)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def connectTwoGroups(self, cost: List[List[int]]) -> int:
        m, n = len(cost), len(cost[0])
        f = [[inf] * (1 << n) for _ in range(m + 1)]
        f[0][0] = 0
        for i in range(1, m + 1):
            for j in range(1 << n):
                for k in range(n):
                    if (j >> k & 1) == 0:
                        continue
                    c = cost[i - 1][k]
                    x = min(f[i][j ^ (1 << k)], f[i - 1][j], f[i - 1][j ^ (1 << k)]) + c
                    f[i][j] = min(f[i][j], x)
        return f[m][-1]

Continue Practicing

#1349 maximum students taking exam #1655 distribute repeating integers #1681 minimum incompatibility