# Minimum Cost to Connect Two Groups of Points
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-cost-to-connect-two-groups-of-points)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-connect-two-groups-of-points
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array, Matrix
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-cost-to-connect-two-groups-of-points/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/minimum-cost-to-connect-two-groups-of-points/image1.jpg) 

**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.length`
* `size2 == cost[i].length`
* `1 <= size1, size2 <= 12`
* `size1 >= size2`
* `0 <= cost[i][j] <= 100`

# Approaches
## Top-Down DP with Brute-Force Connection
This approach uses a top-down dynamic programming (or recursion with memoization) strategy. We define a function that computes the minimum cost for a subproblem and store its result to avoid redundant calculations. The state is defined by the current point `i` in the first group being considered and a bitmask `mask` representing the set of already connected points in the second group.
**Time:** O(size1 * 4^size2). There are `size1 * 2^size2` states. For each state `(i, mask)`, we iterate through `2^size2` subsets `p_mask` for point `i`. This results in a total complexity of `O(size1 * 2^size2 * 2^size2)`. · **Space:** O(size1 * 2^size2) for the memoization table.
**Pros:** The logic is a direct translation of the problem's recursive structure.; It's relatively easier to conceptualize and implement compared to more optimized dynamic programming solutions.
**Cons:** The time complexity is very high due to the exhaustive search over all subsets for each point in group 1.; This approach is likely to exceed the time limit for the given constraints.
### Explanation
The core idea is to build the solution by making decisions for each point in the first group, one by one. Let's define a function `solve(i, mask)` that returns the minimum cost to satisfy the connection criteria for points `i, i+1, ..., size1-1` from group 1, given that the points represented by `mask` in group 2 are already connected by points `0, ..., i-1`.

For each point `i`, we must connect it to at least one point in group 2. We can iterate through all `2^size2 - 1` non-empty subsets of group 2 points. For each subset, we calculate the connection cost for point `i` and recursively call the function for the next point `i+1` with an updated mask. The minimum of these recursive calls will be the answer for the current state.

The base case for the recursion is when we have considered all points from group 1 (`i == size1`). At this point, all group 1 points are connected. We then need to ensure all group 2 points are connected. For any point `j` in group 2 that is not yet connected (i.e., not in `mask`), we must add a connection. To minimize cost, we connect it to the cheapest possible point in group 1. This cost is `min(cost[k][j])` over all `k` from `0` to `size1-1`. We can precompute these minimums for each point in group 2.

Memoization is used to store the results for each state `(i, mask)` to avoid re-computation, which is crucial for passing smaller test cases.

```java
class Solution {
    private int size1, size2;
    private List<List<Integer>> cost;
    private int[] minCostG2;
    private Integer[][] memo;

    public int minCostConnectTwoGroups(List<List<Integer>> cost) {
        this.cost = cost;
        this.size1 = cost.size();
        this.size2 = cost.get(0).size();
        this.minCostG2 = new int[size2];
        
        for (int j = 0; j < size2; j++) {
            int minC = Integer.MAX_VALUE;
            for (int i = 0; i < size1; i++) {
                minC = Math.min(minC, cost.get(i).get(j));
            }
            minCostG2[j] = minC;
        }
        
        this.memo = new Integer[size1][1 << size2];
        return solve(0, 0);
    }

    private int solve(int i, int mask) {
        if (i == size1) {
            int remainingCost = 0;
            for (int j = 0; j < size2; j++) {
                if ((mask & (1 << j)) == 0) {
                    remainingCost += minCostG2[j];
                }
            }
            return remainingCost;
        }

        if (memo[i][mask] != null) {
            return memo[i][mask];
        }

        int res = Integer.MAX_VALUE;
        // Iterate over all non-empty subsets of group 2 for point i
        for (int p_mask = 1; p_mask < (1 << size2); p_mask++) {
            int currentCost = 0;
            for (int j = 0; j < size2; j++) {
                if ((p_mask & (1 << j)) != 0) {
                    currentCost += cost.get(i).get(j);
                }
            }
            res = Math.min(res, currentCost + solve(i + 1, mask | p_mask));
        }

        return memo[i][mask] = res;
    }
}
```
### Algorithm
1. Define a recursive function `solve(i, mask)` which calculates the minimum cost to connect points from index `i` to `size1 - 1` in the first group, given that the points represented by `mask` in the second group are already connected.
2. The state of our recursion is `(i, mask)`, where `i` is the index of the point in group 1 we are considering, and `mask` is a bitmask representing the connected points in group 2.
3. **Base Case:** If `i == size1`, all points from group 1 are connected. However, we must still ensure all points in group 2 are connected. For any point `j` in group 2 not yet covered by `mask`, we must connect it to a point in group 1. To minimize cost, we connect it to the point `k` in group 1 that offers the minimum `cost[k][j]`. We can precompute these minimum costs for each point in group 2. The base case returns the sum of these minimum costs for all unconnected points in group 2.
4. **Recursive Step:** For `solve(i, mask)`, we must connect point `i` from group 1 to at least one point in group 2. We can try connecting point `i` to every possible non-empty subset of points in group 2. Let's call such a subset `p_mask`.
5. For each `p_mask`, calculate the cost of these connections, which is `sum(cost[i][j] for j in p_mask)`. The new mask of connected points in group 2 becomes `mask | p_mask`.
6. The total cost for choosing `p_mask` is `cost_for_p_mask + solve(i + 1, mask | p_mask)`.
7. The function `solve(i, mask)` returns the minimum value over all possible choices of `p_mask`.
8. Use a 2D array `memo[i][mask]` to store the results of `solve(i, mask)` to avoid recomputing for the same state.

## Top-Down DP with Optimized Connection Search
This approach also uses top-down dynamic programming but optimizes the transition step. In the previous approach, for each point `i` in group 1, we iterated through all `2^size2` possible connection subsets, leading to a high time complexity. We can optimize this search for the best connection subset for point `i`.
**Time:** O(size1 * size2 * 2^size2). There are `size1 * 2^size2` states for `solve`. For each state, we compute the transition using a helper function. The helper function `findMinForI` has `size2 * 2^size2` states `(j, p_mask)`, and each state is computed once. So, the transition takes `O(size2 * 2^size2)`. The total complexity is the product of these two. · **Space:** O(size1 * 2^size2). The main memoization table `memo` takes `O(size1 * 2^size2)`. The helper's memoization table `memo_helper` takes `O(size2 * 2^size2)` but is reused for each state of `solve`.
**Pros:** Significantly more efficient than the brute-force transition.; Feasible for the given constraints on `size1` and `size2`.
**Cons:** The implementation is more complex, involving a recursive helper function with its own memoization table within the main recursive function.; Care must be taken with managing the memoization tables for both the main and helper functions.
### Explanation
We can optimize the transition `solve(i, mask)` by creating a helper function that builds the optimal connection for point `i` more efficiently. Instead of a brute-force loop over `2^size2` subsets, this helper function, let's call it `findMinForI`, will decide for each point `j` in group 2 whether to include it in point `i`'s connection set or not.

The helper function `findMinForI(j, p_mask)` would compute the minimum cost for connecting point `i` to a subset of points `{j, ..., size2-1}` given that `i` is already connected to `p_mask` from points `{0, ..., j-1}`. The state of this helper function is `(j, p_mask)`, where `j` is the current point in group 2 being considered, and `p_mask` is the subset of connections for point `i` built so far.

`findMinForI(j, p_mask)`:
- **Base Case:** When `j == size2`, we have considered all points in group 2 for connection to `i`. If `p_mask` is empty, it means `i` was not connected, which is invalid (return infinity). Otherwise, the total cost is `solve(i + 1, mask | p_mask)`.
- **Recursive Step:** For point `j`, we have two choices:
  1. Don't connect `i` to `j`: The cost is `findMinForI(j + 1, p_mask)`.
  2. Connect `i` to `j`: The cost is `cost[i][j] + findMinForI(j + 1, p_mask | (1 << j))`.
- The function returns the minimum of these two choices.

The main `solve(i, mask)` function will call `findMinForI(0, 0)` to find the best connection for point `i`. The helper function `findMinForI` can be memoized on its state `(j, p_mask)`. Since this helper is called within `solve(i, mask)`, its memoization table must be reset for each state `(i, mask)` of the outer recursion.

This optimization reduces the complexity of the transition. For each state `(i, mask)`, we solve a subproblem of size `O(size2 * 2^size2)`. The total complexity becomes `O(size1 * size2 * 2^size2)`.

```java
class Solution {
    private int size1, size2;
    private List<List<Integer>> cost;
    private int[] minCostG2;
    private Integer[][] memo;
    private Integer[][] memo_helper;

    public int minCostConnectTwoGroups(List<List<Integer>> cost) {
        this.cost = cost;
        this.size1 = cost.size();
        this.size2 = cost.get(0).size();
        this.minCostG2 = new int[size2];
        
        for (int j = 0; j < size2; j++) {
            int minC = Integer.MAX_VALUE;
            for (int i = 0; i < size1; i++) {
                minC = Math.min(minC, cost.get(i).get(j));
            }
            minCostG2[j] = minC;
        }
        
        this.memo = new Integer[size1][1 << size2];
        return solve(0, 0);
    }

    private int solve(int i, int mask) {
        if (i == size1) {
            int remainingCost = 0;
            for (int j = 0; j < size2; j++) {
                if ((mask & (1 << j)) == 0) {
                    remainingCost += minCostG2[j];
                }
            }
            return remainingCost;
        }

        if (memo[i][mask] != null) {
            return memo[i][mask];
        }

        // Memoization for the helper function, specific to the state (i, mask)
        // Although 'i' and 'mask' are not passed to findMinForI, they define the context
        // in which it's called. The recursive calls from findMinForI depend on them.
        memo_helper = new Integer[size2 + 1][1 << size2];
        int res = findMinForI(i, mask, 0, 0);
        return memo[i][mask] = res;
    }

    private int findMinForI(int i, int mask, int j, int p_mask) {
        if (j == size2) {
            if (p_mask == 0) {
                return 1_000_000_000; // Invalid path, point i not connected
            }
            return solve(i + 1, mask | p_mask);
        }

        if (memo_helper[j][p_mask] != null) {
            return memo_helper[j][p_mask];
        }

        // Option 1: Don't connect point i to point j
        int res = findMinForI(i, mask, j + 1, p_mask);

        // Option 2: Connect point i to point j
        res = Math.min(res, cost.get(i).get(j) + findMinForI(i, mask, j + 1, p_mask | (1 << j)));
        
        return memo_helper[j][p_mask] = res;
    }
}
```
### Algorithm
1. Define a DP state `dp[mask]` as the minimum cost to connect the first `i` points of group 1 such that the points in group 2 represented by `mask` are covered.
2. We can use a 1D DP array `dp` of size `2^size2` and iterate from `i = 1` to `size1`. The `dp` array at the beginning of iteration `i` will store the results for the first `i-1` points.
3. For each point `i` from group 1, we need to update the `dp` table. Let `dp_prev` be the table for `i-1` points and `dp_curr` be the table for `i` points.
4. The transition is `dp_curr[mask] = min_{prev_mask | p_mask = mask, p_mask > 0} (dp_prev[prev_mask] + cost_for_p_mask)`. Here, `cost_for_p_mask` is the cost to connect point `i-1` to the subset `p_mask` of group 2.
5. This transition is an OR-convolution in min-plus algebra. A naive implementation takes `O(4^size2)` time. We can optimize this using subset convolution techniques.
6. The transition can be rewritten as `dp_curr[mask] = min_{sub ⊂ mask, sub>0} (dp_prev[mask \ sub] + cost_for_sub)`. This is a subset convolution.
7. Subset convolution can be computed efficiently using Sum over Subsets (SOS) DP. The overall complexity for computing one `dp_curr` table from `dp_prev` becomes `O(size2^2 * 2^size2)`.
8. After iterating through all `size1` points, the final answer is not yet `dp[(1<<size2)-1]`. The DP state only ensures that the first `size1` points are connected. We still need to ensure all points in group 2 are connected.
9. A better approach is to use the Top-Down DP from the previous method but optimize the transition for connecting point `i`.
10. Instead of iterating through all `2^size2` subsets for point `i`, we can build the connection subset for `i` recursively. Define a helper function `findMinForI(i, mask, j, p_mask)` that finds the minimum cost by deciding whether to connect `i` to `j` or not, and recursing for `j+1`. This avoids the `O(4^size2)` complexity.
11. The state for this helper function can be memoized. For a fixed `(i, mask)` from the outer recursion, the helper's state is `(j, p_mask)`, leading to an `O(size2 * 2^size2)` transition.

# Solutions
### Java

```java
class Solution {
public
  int connectTwoGroups(List<List<Integer>> cost) {
    int m = cost.size(), n = cost.get(0).size();
    final int inf = 1 << 30;
    int[][] f = new int[m + 1][1 << n];
    for (int[] g : f) {
      Arrays.fill(g, inf);
    }
    f[0][0] = 0;
    for (int i = 1; i <= m; ++i) {
      for (int j = 0; j < 1 << n; ++j) {
        for (int k = 0; k < n; ++k) {
          if ((j >> k & 1) == 1) {
            int c = cost.get(i - 1).get(k);
            f[i][j] = Math.min(f[i][j], f[i][j ^ (1 << k)] + c);
            f[i][j] = Math.min(f[i][j], f[i - 1][j] + c);
            f[i][j] = Math.min(f[i][j], f[i - 1][j ^ (1 << k)] + c);
          }
        }
      }
    }
    return f[m][(1 << n) - 1];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int connectTwoGroups(vector<vector<int>> &cost) {
    int m = cost.size(), n = cost[0].size();
    int f[m + 1][1 << n];
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= m; ++i) {
      for (int j = 0; j < 1 << n; ++j) {
        for (int k = 0; k < n; ++k) {
          if (j >> k & 1) {
            int c = cost[i - 1][k];
            int 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 << n) - 1];
  }
};

```

### Python

```python
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]

```