Minimum Cost to Connect Two Groups of Points — Solution
Minimum Cost to Connect Two Groups of Points solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Cost to Connect Two Groups of Points is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Matrix, Bit Manipulation, Bitmask
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are two groups of points: the first holds size1 points and the second size2 points, with size1 >= size2. The grid cost has size1 rows and size2 columns, and cost[i][j] is the price of drawing a link between point i of the first group and point j of the second.
The groups are connected when every point of the first group is linked to at least one point of the second group, and every point of the second group is linked to at least one point of the first. You may draw any number of links.
Return the minimum total price of a set of links that connects the two groups.
Example 1
Input: cost = [[15,96],[36,2]]
Output: 17
Explanation: Link 1–A for 15 and 2–B for 2: every point is touched, total 17.
Example 2
Input: cost = [[1,3,5],[4,1,1],[1,5,3]]
Output: 4
Explanation: Links 1–A (1), 2–B (1), 2–C (1) and 3–A (1) touch every point for a total of 4.
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] <= 100
Hints for Minimum Cost to Connect Two Groups of Points
Hint 1
A point of the first group never needs two links: if it had a second one, that link only exists to cover some point of the second group, and that point could use its own cheapest link instead.
Hint 2
So walk the first group row by row, give each row exactly one link, and remember which second-group points are already covered — at most
2^12sets.Hint 3
After the last row, every second-group point still uncovered is paid for with its cheapest link from any first-group point. Take the best total over all covered-sets.
How to solve Minimum Cost to Connect Two Groups of Points
Split the links into two kinds: one chosen link per first-group point, and one cheapest link for every second-group point the first kind left uncovered. A DP over first-group rows with a bitmask of covered second-group points prices the first kind; the second kind is a fixed per-column minimum.
Approach
- Precompute
minCol[j], the cheapest link into second-group pointj. - Let
dp[mask]be the cheapest way to give one link to each of the rows handled so far with exactlymaskcovered; start withdp[0] = 0. - For each row
i, build a new table: from every reachablemaskand every columnj, relaxnew[mask | 1<<j]withdp[mask] + cost[i][j]. - At the end, the answer is the minimum over
maskofdp[mask]plusminCol[j]for everyjnot inmask.
Why it works
Take any optimal link set. Every first-group point keeps at least one link; mark one of them per point as its chosen link. Any other link (i, j) exists only to cover j, and is never cheaper than minCol[j], so swapping all such links for the cheapest ones (at most one per uncovered column) keeps the groups connected and never raises the price. The DP enumerates exactly every way to choose one link per row and then pays the cheapest completion, so it reaches that optimum.
Complexity
- Time —
O(size1 * 2^size2 * size2) - Space —
O(2^size2)
Pitfalls
- Covering a second-group point once is enough — paying
minCol[j]for columns already in the mask would double-count. - A row may link to a column that is already covered; the transition must allow
mask | 1<<j == mask. - Costs can be
0, so do not use0as an "unreached" marker.
Reference solution
Python
from typing import List
def connectTwoGroups(cost: List[List[int]]) -> int:
n1, n2 = len(cost), len(cost[0])
full = 1 << n2
INF = float('inf')
min_col = [min(cost[i][j] for i in range(n1)) for j in range(n2)]
dp = [INF] * full
dp[0] = 0
for i in range(n1):
nd = [INF] * full
row = cost[i]
for mask in range(full):
base = dp[mask]
if base == INF:
continue
for j in range(n2):
nm = mask | (1 << j)
v = base + row[j]
if v < nd[nm]:
nd[nm] = v
dp = nd
best = INF
for mask in range(full):
if dp[mask] == INF:
continue
total = dp[mask] + sum(min_col[j] for j in range(n2) if not (mask >> j) & 1)
best = min(best, total)
return bestJava
public static int connectTwoGroups(int[][] cost) {
int n1 = cost.length, n2 = cost[0].length, full = 1 << n2;
final int INF = Integer.MAX_VALUE / 2;
int[] minCol = new int[n2];
Arrays.fill(minCol, INF);
for (int i = 0; i < n1; i++) for (int j = 0; j < n2; j++) minCol[j] = Math.min(minCol[j], cost[i][j]);
int[] dp = new int[full];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int i = 0; i < n1; i++) {
int[] nd = new int[full];
Arrays.fill(nd, INF);
for (int mask = 0; mask < full; mask++) {
if (dp[mask] == INF) continue;
for (int j = 0; j < n2; j++) {
int nm = mask | (1 << j);
nd[nm] = Math.min(nd[nm], dp[mask] + cost[i][j]);
}
}
dp = nd;
}
int best = INF;
for (int mask = 0; mask < full; mask++) {
if (dp[mask] == INF) continue;
int total = dp[mask];
for (int j = 0; j < n2; j++) if ((mask & (1 << j)) == 0) total += minCol[j];
best = Math.min(best, total);
}
return best;
}C++
int connectTwoGroups(vector<vector<int>>& cost) {
int n1 = cost.size(), n2 = cost[0].size(), full = 1 << n2;
const int INF = INT_MAX / 2;
vector<int> minCol(n2, INF);
for (int i = 0; i < n1; i++) for (int j = 0; j < n2; j++) minCol[j] = min(minCol[j], cost[i][j]);
vector<int> dp(full, INF);
dp[0] = 0;
for (int i = 0; i < n1; i++) {
vector<int> nd(full, INF);
for (int mask = 0; mask < full; mask++) {
if (dp[mask] == INF) continue;
for (int j = 0; j < n2; j++) {
int nm = mask | (1 << j);
nd[nm] = min(nd[nm], dp[mask] + cost[i][j]);
}
}
dp = nd;
}
int best = INF;
for (int mask = 0; mask < full; mask++) {
if (dp[mask] == INF) continue;
int total = dp[mask];
for (int j = 0; j < n2; j++) if (!(mask & (1 << j))) total += minCol[j];
best = min(best, total);
}
return best;
}JavaScript
var connectTwoGroups = function(cost) {
var n1 = cost.length, n2 = cost[0].length, full = 1 << n2, INF = 1000000000;
var minCol = [];
for (var j = 0; j < n2; j++) {
var m = INF;
for (var i = 0; i < n1; i++) if (cost[i][j] < m) m = cost[i][j];
minCol.push(m);
}
var dp = new Array(full).fill(INF);
dp[0] = 0;
for (var i = 0; i < n1; i++) {
var nd = new Array(full).fill(INF);
for (var mask = 0; mask < full; mask++) {
if (dp[mask] === INF) continue;
for (var j = 0; j < n2; j++) {
var nm = mask | (1 << j), v = dp[mask] + cost[i][j];
if (v < nd[nm]) nd[nm] = v;
}
}
dp = nd;
}
var best = INF;
for (var mask = 0; mask < full; mask++) {
if (dp[mask] === INF) continue;
var total = dp[mask];
for (var j = 0; j < n2; j++) if (((mask >> j) & 1) === 0) total += minCol[j];
if (total < best) best = total;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming