Minimum Cost to Connect Two Groups of Points

Minimum Cost to Connect Two Groups of Points

What is this problem about?

The Minimum Cost to Connect Two Groups of Points problem gives you two groups of points, and a cost matrix where cost[i][j] is the cost to connect point i from the first group with point j from the second group. You need to find the minimum cost to connect every point in both groups to at least one point in the other group.

Why is this asked in interviews?

This is a high-level Minimum Cost to Connect Groups interview question at Google. It is a classic Bitmask Dynamic Programming problem. It tests if a candidate can handle asymmetrical constraints where one group is small enough (e.g., up to 12 points) to be represented as a bitmask. It evaluates complex state management and optimization.

Algorithmic pattern used

The Bitmask DP interview pattern is required.

1. Let dp[i][mask] be the minimum cost to connect the first i points of group 1, where mask represents the set of points in group 2 that have been connected.
2. For each point i in group 1, you can connect it to any point j in group 2, or even a subset of points.
3. After covering all points in group 1, you might still have some points in group 2 that are not covered. You connect those to their cheapest possible neighbor in group 1.
4. This results in an $O(N \cdot 2^M)$ complexity, where $N$ and $M$ are the sizes of the two groups.

Example explanation

Group 1: {A, B}, Group 2: {X, Y}. Costs: A-X=1, A-Y=5, B-X=5, B-Y=1.

1. Connect A to X (cost 1). Mask of Group 2 covered: {X}.
2. Connect B to Y (cost 1). Mask of Group 2 covered: {X, Y}.
3. All points in both groups are connected. Total cost = 2. If we connected A to X and B to X, Y would be left out and would need a connection, costing more.

Common mistakes candidates make

• Trying Greedy: Connecting each point to its nearest neighbor. This fails because a single expensive connection might satisfy multiple points' requirements later.
• Incorrect Bitmask: Not realizing that all points in both groups must be connected. Some might only cover group 1 and forget to check group 2.
• Ignoring the small constraint: Trying to solve it with a general flow algorithm, which might be overkill or not applicable depending on the "at least one" constraint.

Interview preparation tip

Whenever you see a problem with a very small constraint (like 10-15) on one of the inputs, think of Bitmasks. Practicing Bitmask DP is a great way to prepare for "hard" level interviews at top-tier tech companies.