Minimum cost to connect two groups of points

Array Dynamic Programming Bit Manipulation Matrix Bitmask

49.6% acceptance

Feb 25, 2026

493

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. Return the minimum cost it takes to connect the two groups.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn connect_two_groups(cost: Vec<Vec<i32>>) -> i32 {
    let s1 = cost.len();
    let s2 = cost[0].len();
    // Min cost to connect each point in group 2
    let min2: Vec<i32> = (0..s2).map(|j| (0..s1).map(|i| cost[i][j]).min().unwrap()).collect();
    // dp[mask] = min cost to process all of group1, with group2's coverage = mask
    let full = (1 << s2) - 1usize;
    const INF: i32 = i32::MAX / 2;
    let mut dp = vec![INF; 1 << s2];
    dp[0] = 0;

    for i in 0..s1 {
      let mut new_dp = vec![INF; 1 << s2];
      for mask in 0..=(full) {
        if dp[mask] == INF { continue; }
        for j in 0..s2 {
          let new_mask = mask | (1 << j);
          let ncost = dp[mask] + cost[i][j];
          if ncost < new_dp[new_mask] {
            new_dp[new_mask] = ncost;
          }
        }
      }
      dp = new_dp;
    }

    // For any mask not equal to full, add minimum cost to connect uncovered group2 points
    let mut ans = INF;
    for mask in 0..=full {
      if dp[mask] == INF { continue; }
      let mut extra = 0;
      for j in 0..s2 {
        if mask & (1 << j) == 0 {
          extra += min2[j];
        }
      }
      ans = ans.min(dp[mask] + extra);
    }
    ans
  }
}