#1467Time: 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`.
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.
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
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.
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.
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.
. Here, cost_for_p_mask is the cost to connect point i-1 to the subset p_mask of group 2.
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.
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.
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).
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.
A better approach is to use the Top-Down DP from the previous method but optimize the transition for connecting point i.
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.
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.
Walkthrough
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:
Don't connect i to j: The cost is findMinForI(j + 1, p_mask).
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).
1class Solution {2 private int size1, size2;3 private List<List<Integer>> cost;4 private int[] minCostG2;5 private Integer[][] memo;6 private Integer[][] memo_helper;78 public int minCostConnectTwoGroups(List<List<Integer>> cost) {9 this.cost = cost;10 this.size1 = cost.size();11 this.size2 = cost.get(0).size();12 this.minCostG2 = new int[size2];1314 for (int j = 0; j < size2; j++) {15 int minC = Integer.MAX_VALUE;16 for (int i = 0; i < size1; i++) {17 minC = Math.min(minC, cost.get(i).get(j));18 }19 minCostG2[j] = minC;20 }2122 this.memo = new Integer[size1][1 << size2];23 return solve(0, 0);24 }2526 private int solve(int i, int mask) {27 if (i == size1) {28 int remainingCost = 0;29 for (int j = 0; j < size2; j++) {30 if ((mask & (1 << j)) == 0) {31 remainingCost += minCostG2[j];32 }33 }34 return remainingCost;35 }3637 if (memo[i][mask] != null) {38 return memo[i][mask];39 }4041 // Memoization for the helper function, specific to the state (i, mask)42 // Although 'i' and 'mask' are not passed to findMinForI, they define the context43 // in which it's called. The recursive calls from findMinForI depend on them.44 memo_helper = new Integer[size2 + 1][1 << size2];45 int res = findMinForI(i, mask, 0, 0);46 return memo[i][mask] = res;47 }4849 private int findMinForI(int i, int mask, int j, int p_mask) {50 if (j == size2) {51 if (p_mask == 0) {52 return 1_000_000_000; // Invalid path, point i not connected53 }54 return solve(i + 1, mask | p_mask);55 }5657 if (memo_helper[j][p_mask] != null) {58 return memo_helper[j][p_mask];59 }6061 // Option 1: Don't connect point i to point j62 int res = findMinForI(i, mask, j + 1, p_mask);6364 // Option 2: Connect point i to point j65 res = Math.min(res, cost.get(i).get(j) + findMinForI(i, mask, j + 1, p_mask | (1 << j)));6667 return memo_helper[j][p_mask] = res;68 }69}
Complexity
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`.
Trade-offs
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.
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.
Algorithm
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.
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.
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.
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.
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.
The total cost for choosing p_mask is cost_for_p_mask + solve(i + 1, mask | p_mask).
The function solve(i, mask) returns the minimum value over all possible choices of p_mask.
Use a 2D array memo[i][mask] to store the results of solve(i, mask) to avoid recomputing for the same state.
Walkthrough
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.
1class Solution {2 private int size1, size2;3 private List<List<Integer>> cost;4 private int[] minCostG2;5 private Integer[][] memo;67 public int minCostConnectTwoGroups(List<List<Integer>> cost) {8 this.cost = cost;9 this.size1 = cost.size();10 this.size2 = cost.get(0).size();11 this.minCostG2 = new int[size2];1213 for (int j = 0; j < size2; j++) {14 int minC = Integer.MAX_VALUE;15 for (int i = 0; i < size1; i++) {16 minC = Math.min(minC, cost.get(i).get(j));17 }18 minCostG2[j] = minC;19 }2021 this.memo = new Integer[size1][1 << size2];22 return solve(0, 0);23 }2425 private int solve(int i, int mask) {26 if (i == size1) {27 int remainingCost = 0;28 for (int j = 0; j < size2; j++) {29 if ((mask & (1 << j)) == 0) {30 remainingCost += minCostG2[j];31 }32 }33 return remainingCost;34 }3536 if (memo[i][mask] != null) {37 return memo[i][mask];38 }3940 int res = Integer.MAX_VALUE;41 // Iterate over all non-empty subsets of group 2 for point i42 for (int p_mask = 1; p_mask < (1 << size2); p_mask++) {43 int currentCost = 0;44 for (int j = 0; j < size2; j++) {45 if ((p_mask & (1 << j)) != 0) {46 currentCost += cost.get(i).get(j);47 }48 }49 res = Math.min(res, currentCost + solve(i + 1, mask | p_mask));50 }5152 return memo[i][mask] = res;53 }54}
Complexity
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.
Trade-offs
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.
Solutions
Solution
1class Solution {2public3 int connectTwoGroups(List<List<Integer>> cost) {4 int m = cost.size(), n = cost.get(0).size();5 final int inf = 1 << 30;6 int[][] f = new int[m + 1][1 << n];7 for (int[] g : f) {8 Arrays.fill(g, inf);9 }10 f[0][0] = 0;11 for (int i = 1; i <= m; ++i) {12 for (int j = 0; j < 1 << n; ++j) {13 for (int k = 0; k < n; ++k) {14 if ((j >> k & 1) == 1) {15 int c = cost.get(i - 1).get(k);16 f[i][j] = Math.min(f[i][j], f[i][j ^ (1 << k)] + c);17 f[i][j] = Math.min(f[i][j], f[i - 1][j] + c);18 f[i][j] = Math.min(f[i][j], f[i - 1][j ^ (1 << k)] + c);19 }20 }21 }22 }23 return f[m][(1 << n) - 1];24 }25}
1class Solution {2public:3 int connectTwoGroups(vector<vector<int>> &cost) {4 int m = cost.size(), n = cost[0].size();5 int f[m + 1][1 << n];6 memset(f, 0x3f, sizeof(f));7 f[0][0] = 0;8 for (int i = 1; i <= m; ++i) {9 for (int j = 0; j < 1 << n; ++j) {10 for (int k = 0; k < n; ++k) {11 if (j >> k & 1) {12 int c = cost[i - 1][k];13 int x =14 min({f[i][j ^ (1 << k)], f[i - 1][j], f[i - 1][j ^ (1 << k)]}) +15 c;16 f[i][j] = min(f[i][j], x);17 }18 }19 }20 }21 return f[m][(1 << n) - 1];22 }23};
1class Solution:2 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]
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.
