Minimum Cost to Connect Two Groups of Points solution and explanation
Google
8 more videos on this problem
花花酱 LeetCode 1595. Minimum Cost to Connect Two Groups of Points - 刷题找工作 EP358Hua Hua · 11:47 · 2K views
LeetCode 1595. Minimum Cost to Connect Two Groups of PointsHappy Coding · 31:08 · 1K views
Leetcode Solutions 1595. Minimum Cost to Connect Two Groups of PointsAbrar Sher · 16:17 · 1K views
1595. Minimum Cost to Connect Two Groups of Points (Leetcode Hard)Programming Live with Larry · 35:34 · 699 views
【每日一题】LeetCode 1595. Minimum Cost to Connect Two Groups of PointsHuifeng Guan · 42:25 · 532 views
1595 Minimum Cost to Connect Two Groups of Points (Problem Explanation)Sloppy Guy · 14:18 · 286 views
1595. Minimum Cost to Connect Two Groups of Points || LeetCode The Hard WayLeetCode The Hard Way · 10:32 · 153 views
LeetCode Hard 1595 Minimum Cost to Connect Two Groups of Pointsrobzingcod · 8:16 · 25 views
LeetCode 1595: Minimum Cost to Connect Two Groups of PointsAlitaCode · 32:43 · 21 views
The 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:
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.
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
Approach overview
Problem Overview: You are given a cost matrix where cost[i][j] represents the cost of connecting point i from group 1 to point j from group 2. Every point in both groups must be connected to at least one point in the opposite group. The goal is to minimize the total connection cost.
Approach 1: Recursive Backtracking with Caching (O(m * n * 2^n) time, O(m * 2^n) space)
This approach explores all ways to connect points from group 1 to group 2 using recursion. At each step, you choose a connection between the current point in group 1 and any point in group 2, tracking which group‑2 points are already connected using a bitmask. Memoization caches results for states defined by (index, mask) to avoid recomputation. After processing all group‑1 points, any group‑2 point not yet connected is attached using its minimum possible cost. This reduces the exponential search space significantly and works well within the constraints.
Approach 2: Dynamic Programming with Bitmask (O(m * n * 2^n) time, O(2^n) space)
This is the optimized solution typically expected in interviews. Use a DP state where dp[mask] represents the minimum cost after connecting some points in group 1 such that the set of connected points in group 2 equals mask. Iterate through each point in group 1 and update the DP by trying connections to every point in group 2. Bit operations track which points are already connected. Precompute the minimum cost for connecting each group‑2 point so that any remaining unconnected points can be handled at the end. The key insight is representing connection states compactly with a bitmask and progressively building optimal solutions.
The DP formulation relies heavily on dynamic programming and bitmask techniques to compress state space. The input itself is modeled as a matrix, where each entry represents a possible connection cost.
Recommended for interviews: Dynamic Programming with Bitmask is the expected solution. It demonstrates strong state modeling and efficient subset processing. The recursive solution with caching is easier to reason about initially and helps verify correctness, but the iterative DP version shows stronger control over state transitions and space optimization.
Approach 1: Dynamic Programming with Mask
This approach uses a dynamic programming strategy, specifically leveraging a mask to represent which points in the second group have been connected. The state in our DP table will keep track of the minimal cost to connect a certain number of points from the first group to the desired points in the second group. The largest runtime occurs when we compute the transition costs, but overall the approach is feasible due to small group sizes.
from functools import lru_cache
class Solution:
def connectTwoGroups(self, cost):
size1, size2 = len(cost), len(cost[0])
@lru_cache(None)
def dp(i, j_mask):
if i == size1:
return sum(min(cost[k][j] for k in range(size1)) for j in range(size2) if not j_mask & (1 << j))
min_cost = float('inf')
for j in range(size2):
min_cost = min(min_cost, cost[i][j] + dp(i + 1, j_mask | (1 << j)))
return min_cost
return dp(0, 0)
def main():
solution = Solution()
cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
print(solution.connectTwoGroups(cost))
main()import java.util.Arrays;
public class MinCostConnectPoints {
public static int minCostConnectPoints(int[][] cost) {
int size1 = cost.length, size2 = cost[0].length;
int maxMask = 1 << size2;
int[][] dp = new int[size1 + 1][maxMask];
for (int[] row : dp)
Arrays.fill(row, Integer.MAX_VALUE);
dp[0][0] = 0;
for (int i = 0; i < size1; ++i) {
for (int mask = 0; mask < maxMask; ++mask) {
for (int j = 0; j < size2; ++j) {
int newMask = mask | (1 << j);
dp[i + 1][newMask] = Math.min(dp[i + 1][newMask], dp[i][mask] + cost[i][j]);
}
}
}
int result = Integer.MAX_VALUE;
for (int mask = 0; mask < maxMask; ++mask) {
int temp = dp[size1][mask];
for (int j = 0; j < size2; ++j) {
if ((mask & (1 << j)) == 0) {
int minAdd = Integer.MAX_VALUE;
for (int i = 0; i < size1; ++i) {
minAdd = Math.min(minAdd, cost[i][j]);
}
temp += minAdd;
}
}
result = Math.min(result, temp);
}
return result;
}
public static void main(String[] args) {
int[][] cost = {{1, 3, 5}, {4, 1, 1}, {1, 5, 3}};
int result = minCostConnectPoints(cost);
System.out.println(result);
}
}#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int minCostConnectPoints(vector<vector<int>>& cost) {
int size1 = cost.size(), size2 = cost[0].size();
vector<vector<int>> dp(size1 + 1, vector<int>((1 << size2), INT_MAX));
dp[0][0] = 0;
for (int i = 0; i < size1; ++i) {
for (int mask = 0; mask < (1 << size2); ++mask) {
for (int j = 0; j < size2; ++j) {
int newMask = mask | (1 << j);
dp[i + 1][newMask] = min(dp[i + 1][newMask], dp[i][mask] + cost[i][j]);
}
}
}
int result = INT_MAX;
for (int mask = 0; mask < (1 << size2); ++mask) {
int temp = dp[size1][mask];
for (int j = 0; j < size2; ++j) {
if (!(mask & (1 << j))) {
int minAdd = INT_MAX;
for (int i = 0; i < size1; ++i) {
minAdd = min(minAdd, cost[i][j]);
}
temp += minAdd;
}
}
result = min(result, temp);
}
return result;
}
int main() {
vector<vector<int>> cost = {{1, 3, 5}, {4, 1, 1}, {1, 5, 3}};
cout << minCostConnectPoints(cost) << endl;
return 0;
}function connectTwoGroups(cost) {
const size1 = cost.length;
const size2 = cost[0].length;
const maxMask = 1 << size2;
const dp = Array.from({ length: size1 + 1 }, () => Array(maxMask).fill(Infinity));
dp[0][0] = 0;
for (let i = 0; i < size1; i++) {
for (let mask = 0; mask < maxMask; mask++) {
for (let j = 0; j < size2; j++) {
const newMask = mask | (1 << j);
dp[i + 1][newMask] = Math.min(dp[i + 1][newMask], dp[i][mask] + cost[i][j]);
}
}
}
let result = Infinity;
for (let mask = 0; mask < maxMask; mask++) {
let temp = dp[size1][mask];
for (let j = 0; j < size2; j++) {
if ((mask & (1 << j)) === 0) {
let minAdd = Infinity;
for (let i = 0; i < size1; i++) {
minAdd = Math.min(minAdd, cost[i][j]);
}
temp += minAdd;
}
}
result = Math.min(result, temp);
}
return result;
}
console.log(connectTwoGroups([[1,3,5],[4,1,1],[1,5,3]]));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int minCostConnectPoints(int** cost, int size1, int size2) {
int maxMask = 1 << size2; // 2^size2
int dp[13][4096];
for (int i = 0; i <= size1; ++i) {
for (int j = 0; j < maxMask; ++j) {
dp[i][j] = INT_MAX;
}
}
dp[0][0] = 0;
for (int i = 0; i < size1; ++i) {
for (int mask = 0; mask < maxMask; ++mask) {
for (int j = 0; j < size2; ++j) {
int newMask = mask | (1 << j);
dp[i + 1][newMask] = fmin(dp[i + 1][newMask], dp[i][mask] + cost[i][j]);
}
}
}
int result = INT_MAX;
for (int mask = 0; mask < maxMask; ++mask) {
int temp = dp[size1][mask];
for (int j = 0; j < size2; ++j) {
if (!(mask & (1 << j))) {
int minAdd = INT_MAX;
for (int i = 0; i < size1; ++i) {
minAdd = fmin(minAdd, cost[i][j]);
}
temp += minAdd;
}
}
result = fmin(result, temp);
}
return result;
}
int main() {
int* cost[] = {(int[]){1,3,5}, (int[]){4,1,1}, (int[]){1,5,3}};
int size1 = 3, size2 = 3;
printf("%d\n", minCostConnectPoints(cost, size1, size2));
return 0;
}using System;
using System.Linq;
using System.Collections.Generic;
public class Solution {
public int ConnectTwoGroups(IList<IList<int>> cost) {
int size1 = cost.Count;
int size2 = cost[0].Count;
var dp = new int[size1 + 1, 1 << size2];
for (int i = 0; i <= size1; i++)
for (int j = 0; j < (1 << size2); j++)
dp[i, j] = int.MaxValue;
dp[0, 0] = 0;
for (int i = 0; i < size1; i++) {
for (int mask = 0; mask < (1 << size2); mask++) {
for (int j = 0; j < size2; j++) {
int newMask = mask | (1 << j);
dp[i + 1, newMask] = Math.Min(dp[i + 1, newMask], dp[i, mask] + cost[i][j]);
}
}
}
int result = int.MaxValue;
for (int mask = 0; mask < (1 << size2); mask++) {
int temp = dp[size1, mask];
for (int j = 0; j < size2; j++) {
if ((mask & (1 << j)) == 0) {
int minAdd = int.MaxValue;
for (int i = 0; i < size1; i++) {
minAdd = Math.Min(minAdd, cost[i][j]);
}
temp += minAdd;
}
}
result = Math.Min(result, temp);
}
return result;
}
public static void Main(string[] args) {
var cost = new List<IList<int>>() {
new List<int> {1, 3, 5},
new List<int> {4, 1, 1},
new List<int> {1, 5, 3}
};
Solution sol = new Solution();
Console.WriteLine(sol.ConnectTwoGroups(cost));
}
}This Python solution uses memoization via functools' lru_cache feature, simplifying the recursive DP pattern. The critical computation is made succinct with decorators, maintaining clarity without overwhelming with nested loop syntax.
Time Complexity: O(size1 * size2 * 2^size2)
Each decision state pulls recursion with cumulative outcomes, scaled by all group connections.
Space Complexity: O(size1 * 2^size2)
Memoized values from decorated functions lie in cache proportional to time complexity.
Approach 2: Recursive Backtracking with Caching
This method employs recursive backtracking to explore every possible way of connecting points from the first group to the second group. Caching intermediate results helps prevent redundant computations, suitable for this problem size, allowing the recursion to operate within feasible limits.
class Solution:
def __init__(self):
self.cache = {}
def connectTwoGroups(self, cost):
size1, size2 = len(cost), len(cost[0])
return self.dfs(cost, 0, 0, size1, size2)
def dfs(self, cost, i, mask, size1, size2):
if i == size1:
return sum(min(cost[k][j] for k in range(size1)) for j in range(size2) if not mask & (1 << j))
if (i, mask) in self.cache:
return self.cache[(i, mask)]
ans = float('inf')
for j in range(size2):
ans = min(ans, cost[i][j] + self.dfs(cost, i + 1, mask | (1 << j), size1, size2))
self.cache[(i, mask)] = ans
return ans
def main():
solver = Solution()
cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
print(solver.connectTwoGroups(cost))
main()import java.util.Arrays;
public class MinCostConnectPoints {
private Integer[][] cache;
public int minCostConnectPoints(int[][] cost) {
int size1 = cost.length, size2 = cost[0].length;
cache = new Integer[size1][1 << size2];
return dfs(cost, 0, 0, size1, size2);
}
private int dfs(int[][] cost, int i, int mask, int size1, int size2) {
if (i == size1) {
int minCost = 0;
for (int j = 0; j < size2; j++) {
if ((mask & (1 << j)) == 0) {
int localMin = Integer.MAX_VALUE;
for (int k = 0; k < size1; k++) {
localMin = Math.min(localMin, cost[k][j]);
}
minCost += localMin;
}
}
return minCost;
}
if (cache[i][mask] != null) return cache[i][mask];
int ans = Integer.MAX_VALUE;
for (int j = 0; j < size2; j++) {
int newAns = cost[i][j] + dfs(cost, i + 1, mask | (1 << j), size1, size2);
ans = Math.min(ans, newAns);
}
return cache[i][mask] = ans;
}
public static void main(String[] args) {
MinCostConnectPoints sol = new MinCostConnectPoints();
int[][] cost = {{1, 3, 5}, {4, 1, 1}, {1, 5, 3}};
System.out.println(sol.minCostConnectPoints(cost));
}
}#include <iostream>
#include <vector>
#include <cstring>
#include <climits>
using namespace std;
int cache[13][1 << 13];
int dfs(vector<vector<int>>& cost, int i, int mask, int size1, int size2) {
if (i == size1) {
int minCost = 0;
for (int j = 0; j < size2; ++j) {
if (!(mask & (1 << j))) {
int localMin = INT_MAX;
for (int k = 0; k < size1; ++k) {
localMin = min(localMin, cost[k][j]);
}
minCost += localMin;
}
}
return minCost;
}
if (cache[i][mask] != -1) return cache[i][mask];
int ans = INT_MAX;
for (int j = 0; j < size2; ++j) {
ans = min(ans, cost[i][j] + dfs(cost, i + 1, mask | (1 << j), size1, size2));
}
cache[i][mask] = ans;
return ans;
}
int minCostConnectPoints(vector<vector<int>>& cost) {
int size1 = cost.size(), size2 = cost[0].size();
memset(cache, -1, sizeof(cache));
return dfs(cost, 0, 0, size1, size2);
}
int main() {
vector<vector<int>> cost{{1, 3, 5}, {4, 1, 1}, {1, 5, 3}};
cout << minCostConnectPoints(cost) << endl;
return 0;
}class Solution {
constructor() {
this.cache = {};
}
connectTwoGroups(cost) {
const size1 = cost.length;
const size2 = cost[0].length;
return this.dfs(cost, 0, 0, size1, size2);
}
dfs(cost, i, mask, size1, size2) {
if (i === size1) {
let minCost = 0;
for (let j = 0; j < size2; j++) {
if ((mask & (1 << j)) === 0) {
let localMin = Infinity;
for (let k = 0; k < size1; k++) {
localMin = Math.min(localMin, cost[k][j]);
}
minCost += localMin;
}
}
return minCost;
}
const state = `${i},${mask}`;
if (this.cache[state] !== undefined) return this.cache[state];
let ans = Infinity;
for (let j = 0; j < size2; j++) {
ans = Math.min(ans, cost[i][j] + this.dfs(cost, i + 1, mask | (1 << j), size1, size2));
}
return this.cache[state] = ans;
}
}
const solution = new Solution();
const cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]];
console.log(solution.connectTwoGroups(cost));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
int cache[13][1 << 13];
int dfs(int** cost, int i, int mask, int size1, int size2) {
if (i == size1) {
int minCost = 0;
for (int j = 0; j < size2; ++j) {
if (!(mask & (1 << j))) {
int localMin = INT_MAX;
for (int k = 0; k < size1; ++k) {
if (cost[k][j] < localMin) localMin = cost[k][j];
}
minCost += localMin;
}
}
return minCost;
}
if (cache[i][mask] != -1) return cache[i][mask];
int ans = INT_MAX;
for (int j = 0; j < size2; ++j) {
ans = fmin(ans, cost[i][j] + dfs(cost, i + 1, mask | (1 << j), size1, size2));
}
cache[i][mask] = ans;
return ans;
}
int minCostConnectPoints(int** cost, int size1, int size2) {
memset(cache, -1, sizeof(cache));
return dfs(cost, 0, 0, size1, size2);
}
int main() {
int* cost[] = {(int[]){1,3,5}, (int[]){4,1,1}, (int[]){1,5,3}};
int size1 = 3, size2 = 3;
printf("%d\n", minCostConnectPoints(cost, size1, size2));
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
private Dictionary<(int, int), int> cache;
public int ConnectTwoGroups(IList<IList<int>> cost) {
int size1 = cost.Count, size2 = cost[0].Count;
cache = new Dictionary<(int, int), int>();
return Dfs(cost, 0, 0, size1, size2);
}
private int Dfs(IList<IList<int>> cost, int i, int mask, int size1, int size2) {
if (i == size1) {
int minCost = 0;
for (int j = 0; j < size2; j++) {
if ((mask & (1 << j)) == 0) {
int localMin = int.MaxValue;
for (int k = 0; k < size1; k++) {
localMin = Math.Min(localMin, cost[k][j]);
}
minCost += localMin;
}
}
return minCost;
}
if (cache.ContainsKey((i, mask))) return cache[(i, mask)];
int ans = int.MaxValue;
for (int j = 0; j < size2; j++) {
ans = Math.Min(ans, cost[i][j] + Dfs(cost, i + 1, mask | (1 << j), size1, size2));
}
return cache[(i, mask)] = ans;
}
public static void Main(string[] args) {
var cost = new List<IList<int>>() {
new List<int> {1, 3, 5},
new List<int> {4, 1, 1},
new List<int> {1, 5, 3}
};
Solution sol = new Solution();
Console.WriteLine(sol.ConnectTwoGroups(cost));
}
}Python's innate dictionary cacheing simplifies the state tracking necessary for recursion. The solution trades syntactic simplicity for a dynamic table setup, improving gaze and limiting design-overhead flow.
Time Complexity: O(size1 * size2 * 2^size2)
Optimized through recursive cache recurrence for full group connections.
Space Complexity: O(size1 * 2^size2)
Power-set index storage assists calculation tractability and overhead processing.
Approach 3: Bitmask Dynamic Programming
Let m and n denote the number of points in the first group and the second group, respectively.
Since 1 leq n leq m leq 12, we can use an integer to represent the state of points in the second group — specifically, a binary integer of length n, where bit k being 1 means the k-th point in the second group is connected to some point in the first group, and 0 means it is not.
Next, we define f[i][j] as the minimum cost when the first i points in the first group are all connected, and the state of points in the second group is j. Initially, f[0][0] = 0 and all other values are positive infinity. The answer is f[m][2^n - 1].
Consider f[i][j] where i geq 1. We enumerate each point k in the second group. If point k is connected to the i-th point in the first group, we discuss the following two cases:
- If point
kis only connected to thei-th point in the first group, thenf[i][j]can be transitioned fromf[i][j \oplus 2^k]orf[i - 1][j \oplus 2^k], where\oplusdenotes the XOR operation; - If point
kis connected to thei-th point in the first group as well as other points, thenf[i][j]can be transitioned fromf[i - 1][j].
In both cases, we take the minimum transition value:
$
f[i][j] = min_{k \in {0, 1, cdots, n - 1}} {f[i][j \oplus 2^k], f[i - 1][j \oplus 2^k], f[i - 1][j]} + cost[i - 1][k]
Finally, we return f[m][2^n - 1].
The time complexity is O(m times n times 2^n) and the space complexity is O(m times 2^n), where m and n$ are the number of points in the first group and the second group, respectively.
function connectTwoGroups(cost: number[][]): number {
const m = cost.length;
const n = cost[0].length;
const inf = 1 << 30;
const f = Array.from({ length: m + 1 }, () => Array(1 << n).fill(inf));
f[0][0] = 0;
for (let i = 1; i <= m; ++i) {
for (let j = 0; j < 1 << n; ++j) {
for (let k = 0; k < n; ++k) {
if (((j >> k) & 1) === 1) {
const c = cost[i - 1][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];
}func connectTwoGroups(cost [][]int) int {
m, n := len(cost), len(cost[0])
const inf = 1 << 30
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, 1<<n)
for j := range f[i] {
f[i][j] = inf
}
}
f[0][0] = 0
for i := 1; i <= m; i++ {
for j := 0; j < 1<<n; j++ {
for k := 0; k < n; k++ {
c := cost[i-1][k]
if j>>k&1 == 1 {
f[i][j] = min(f[i][j], f[i][j^(1<<k)]+c)
f[i][j] = min(f[i][j], f[i-1][j]+c)
f[i][j] = min(f[i][j], f[i-1][j^(1<<k)]+c)
}
}
}
}
return f[m][(1<<n)-1]
}impl Solution {
pub fn connect_two_groups(cost: Vec<Vec<i32>>) -> i32 {
let m = cost.len();
let n = cost[0].len();
let inf = 1 << 30;
let mut f = vec![vec![inf; 1 << n]; m + 1];
f[0][0] = 0;
for i in 1..=m {
for j in 0..(1 << n) {
for k in 0..n {
if (j >> k) & 1 == 1 {
let c = cost[i - 1][k];
f[i][j] = f[i][j].min(f[i][j ^ (1 << k)] + c);
f[i][j] = f[i][j].min(f[i - 1][j] + c);
f[i][j] = f[i][j].min(f[i - 1][j ^ (1 << k)] + c);
}
}
}
}
f[m][(1 << n) - 1]
}
}Approach 4: 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).
function connectTwoGroups(cost: number[][]): number {
const m = cost.length;
const n = cost[0].length;
const inf = 1 << 30;
const f: number[] = new Array(1 << n).fill(inf);
f[0] = 0;
const g = new Array(1 << n).fill(0);
for (let i = 1; i <= m; ++i) {
for (let j = 0; j < 1 << n; ++j) {
g[j] = inf;
for (let k = 0; k < n; ++k) {
if (((j >> k) & 1) === 1) {
const c = cost[i - 1][k];
g[j] = Math.min(g[j], g[j ^ (1 << k)] + c);
g[j] = Math.min(g[j], f[j] + c);
g[j] = Math.min(g[j], f[j ^ (1 << k)] + c);
}
}
}
f.splice(0, f.length, ...g);
}
return f[(1 << n) - 1];
}func connectTwoGroups(cost [][]int) int {
m, n := len(cost), len(cost[0])
const inf = 1 << 30
f := make([]int, 1<<n)
for i := range f {
f[i] = inf
}
f[0] = 0
g := make([]int, 1<<n)
for i := 1; i <= m; i++ {
for j := 0; j < 1<<n; j++ {
g[j] = inf
for k := 0; k < n; k++ {
c := cost[i-1][k]
if j>>k&1 == 1 {
g[j] = min(g[j], g[j^1<<k]+c)
g[j] = min(g[j], f[j]+c)
g[j] = min(g[j], f[j^1<<k]+c)
}
}
}
copy(f, g)
}
return f[1<<n-1]
}impl Solution {
pub fn connect_two_groups(cost: Vec<Vec<i32>>) -> i32 {
let m = cost.len();
let n = cost[0].len();
let inf = 1 << 30;
let mut f = vec![inf; 1 << n];
f[0] = 0;
let mut g = f.clone();
for i in 1..=m {
for j in 0..(1 << n) {
g[j] = inf;
for k in 0..n {
if (j >> k) & 1 == 1 {
let c = cost[i - 1][k];
g[j] = g[j].min(g[j ^ (1 << k)] + c);
g[j] = g[j].min(f[j] + c);
g[j] = g[j].min(f[j ^ (1 << k)] + c);
}
}
}
f.clone_from_slice(&g);
}
f[(1 << n) - 1]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Mask | Time Complexity: O(size1 * size2 * 2^size2) |
| Recursive Backtracking with Caching | Time Complexity: O(size1 * size2 * 2^size2) |
| Bitmask Dynamic Programming | – |
| Bitmask Dynamic Programming (Space Optimization) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking with Caching | O(m * n * 2^n) | O(m * 2^n) | Good for understanding the state transitions and building intuition before optimizing |
| Dynamic Programming with Bitmask | O(m * n * 2^n) | O(2^n) | Best general solution for constraints up to 12 points per group |
Frequently asked questions
Is Minimum Cost to Connect Two Groups of Points easy or hard?
Minimum Cost to Connect Two Groups of Points is classified as a Hard problem on LeetCode. It requires understanding subset DP and bitmask state representation, which are advanced techniques commonly used in high‑level algorithm interviews.
Minimum Cost to Connect Two Groups of Points Python/Java solution
Most implementations use dynamic programming with a bitmask. The same algorithm works across Python, Java, C++, and JavaScript by storing DP states for each mask and iterating through possible connections. Python solutions often use lists or dictionaries for memoization, while Java and C++ typically use arrays.
What is the best approach for Minimum Cost to Connect Two Groups of Points?
Dynamic Programming with Bitmask is the most efficient and commonly accepted approach. It tracks which points in the second group are connected using a bitmask and iteratively updates the minimum cost while processing each point in the first group. This reduces redundant computation and solves the problem in O(m * n * 2^n) time.
How to solve Minimum Cost to Connect Two Groups of Points in O(m * n * 2^n)?
Use dynamic programming with a bitmask representing which points in group 2 are already connected. For each point in group 1, iterate through all masks and attempt connections to every point in group 2. Update the DP state with the minimum cost while expanding the mask using bit operations.
Is Minimum Cost to Connect Two Groups of Points asked at Google/Amazon/Meta?
Problems involving bitmask dynamic programming and cost matrices frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require connecting groups or covering nodes with minimum cost are common advanced DP interview questions.
What data structure is used in Minimum Cost to Connect Two Groups of Points?
The solution primarily uses arrays for the cost matrix and dynamic programming table. A bitmask integer is used to represent subsets of connected points in group 2, enabling efficient state transitions using bit manipulation.
What is the time complexity of Minimum Cost to Connect Two Groups of Points?
The optimal solution runs in O(m * n * 2^n) time, where m is the size of group 1 and n is the size of group 2. Each DP state represents a subset of connected points in group 2, and transitions consider connecting the current point to any of the n options.