Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1595. Minimum Cost to Connect Two Groups of Points - Leetcode Solution

Code Implementation

from functools import lru_cache

class Solution:
    def connectTwoGroups(self, cost):
        m, n = len(cost), len(cost[0])
        @lru_cache(None)
        def dp(i, mask):
            if i == m:
                # All group1 done, connect any unconnected group2
                res = 0
                for j in range(n):
                    if not (mask & (1 << j)):
                        res += min(cost[k][j] for k in range(m))
                return res
            res = float('inf')
            for j in range(n):
                res = min(res, cost[i][j] + dp(i+1, mask | (1 << j)))
            return res
        return dp(0, 0)
      
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    int connectTwoGroups(vector<vector<int>>& cost) {
        int m = cost.size(), n = cost[0].size();
        int MAX = 1 << n;
        vector<vector<int>> dp(m+1, vector<int>(MAX, INT_MAX/2));
        dp[0][0] = 0;
        for (int i = 0; i < m; ++i) {
            for (int mask = 0; mask < MAX; ++mask) {
                if (dp[i][mask] >= INT_MAX/2) continue;
                for (int j = 0; j < n; ++j) {
                    int new_mask = mask | (1 << j);
                    dp[i+1][new_mask] = min(dp[i+1][new_mask], dp[i][mask] + cost[i][j]);
                }
            }
        }
        int res = INT_MAX;
        for (int mask = 0; mask < MAX; ++mask) {
            int val = dp[m][mask];
            for (int j = 0; j < n; ++j) {
                if (!(mask & (1 << j))) {
                    int minc = INT_MAX;
                    for (int i = 0; i < m; ++i)
                        minc = min(minc, cost[i][j]);
                    val += minc;
                }
            }
            res = min(res, val);
        }
        return res;
    }
};
      
import java.util.*;

class Solution {
    public int connectTwoGroups(List<List<Integer>> cost) {
        int m = cost.size(), n = cost.get(0).size();
        int MAX = 1 << n;
        int[][] dp = new int[m+1][MAX];
        for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
        dp[0][0] = 0;
        for (int i = 0; i < m; ++i) {
            for (int mask = 0; mask < MAX; ++mask) {
                if (dp[i][mask] >= Integer.MAX_VALUE / 2) continue;
                for (int j = 0; j < n; ++j) {
                    int new_mask = mask | (1 << j);
                    dp[i+1][new_mask] = Math.min(dp[i+1][new_mask], dp[i][mask] + cost.get(i).get(j));
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int mask = 0; mask < MAX; ++mask) {
            int val = dp[m][mask];
            for (int j = 0; j < n; ++j) {
                if ((mask & (1 << j)) == 0) {
                    int minc = Integer.MAX_VALUE;
                    for (int i = 0; i < m; ++i)
                        minc = Math.min(minc, cost.get(i).get(j));
                    val += minc;
                }
            }
            res = Math.min(res, val);
        }
        return res;
    }
}
      
var connectTwoGroups = function(cost) {
    const m = cost.length, n = cost[0].length;
    const MAX = 1 << n;
    const dp = Array.from({length: m+1}, () => Array(MAX).fill(Infinity));
    dp[0][0] = 0;
    for (let i = 0; i < m; ++i) {
        for (let mask = 0; mask < MAX; ++mask) {
            if (dp[i][mask] === Infinity) continue;
            for (let j = 0; j < n; ++j) {
                let new_mask = mask | (1 << j);
                dp[i+1][new_mask] = Math.min(dp[i+1][new_mask], dp[i][mask] + cost[i][j]);
            }
        }
    }
    let res = Infinity;
    for (let mask = 0; mask < MAX; ++mask) {
        let val = dp[m][mask];
        for (let j = 0; j < n; ++j) {
            if ((mask & (1 << j)) === 0) {
                let minc = Infinity;
                for (let i = 0; i < m; ++i)
                    minc = Math.min(minc, cost[i][j]);
                val += minc;
            }
        }
        res = Math.min(res, val);
    }
    return res;
};

Problem Description

Given two groups of points, group1 and group2, and a cost matrix cost where cost[i][j] is the cost of connecting the i-th point in group1 to the j-th point in group2, your task is to connect every point in both groups such that:
  • Every point in group1 is connected to at least one point in group2.
  • Every point in group2 is connected to at least one point in group1.
  • You may connect a point in one group to multiple points in the other group.
  • You cannot connect a point to itself (since groups are disjoint).
  • The goal is to minimize the total cost of the connections.

The input is a 2D integer array cost of size m x n where m and n are the sizes of group1 and group2 respectively.

Thought Process

When approaching this problem, the first idea is to try all possible combinations of connections between the two groups, but this quickly becomes infeasible as the number of points increases. Since each point in both groups must be connected at least once, we need a way to efficiently track which points have been connected and minimize the total cost.

The key insight is that this is a type of set covering problem, where we want to cover all points in both groups, and each connection has an associated cost. Because the groups are small (as per Leetcode constraints), we can use bitmasking to represent which points in group2 have been connected so far, and use dynamic programming to avoid redundant calculations.

The conceptual shift is from brute-force (try every possible set of connections) to a dynamic programming approach that builds up solutions incrementally, using memoization to store and reuse results for subproblems.

Solution Approach

To solve the problem efficiently, we use dynamic programming with bitmasking. Here’s how the solution works, step by step:
  1. State Representation:
    • Let i be the index of the current point in group1 we are processing.
    • Let mask be a bitmask representing which points in group2 have already been connected.
  2. Recurrence Relation:
    • For each point i in group1, try connecting it to every point j in group2.
    • For each connection, update the mask to include j and recursively process the next point in group1.
  3. Base Case:
    • When all points in group1 have been processed (i == m), check if there are any points in group2 not yet connected (i.e., bits in mask are 0).
    • For each unconnected point in group2, connect it to the cheapest point in group1 (choose the minimum cost in its column).
  4. Memoization:
    • Store results for each (i, mask) pair to avoid redundant calculations.
  5. Initialization:
    • Start with i = 0 and mask = 0 (no points in group2 connected yet).
  6. Result:
    • The minimum cost returned by the DP function is the answer.

This approach is justified because the number of possible masks is at most 2^n (where n is up to 12), making it feasible for dynamic programming.

Example Walkthrough

Suppose cost = [[1,3,5],[4,1,1],[1,5,3]].
Here, group1 has 3 points, group2 has 3 points.

  1. Start with the first point in group1 (i=0), try connecting to each point in group2 (j=0,1,2):
    • Connect to j=0: cost=1, new mask=001
    • Connect to j=1: cost=3, new mask=010
    • Connect to j=2: cost=5, new mask=100
  2. For each choice, move to the next point in group1 (i=1), and repeat, updating the mask each time.
  3. Continue until all points in group1 are processed (i=3).
  4. At the end, for each mask, check if all points in group2 are covered. If not, connect the remaining ones at minimum additional cost.
  5. The DP will find the combination of connections that covers both groups at the lowest total cost.

The optimal solution for this input is 4 (connect 0->0, 1->1, 2->2).

Time and Space Complexity

  • Brute-force approach:
    • Would try all possible assignments of group1 to group2, which is n^m (exponential and infeasible for large n,m).
  • Optimized DP approach:
    • There are m possible indices for group1 and 2^n possible masks for group2.
    • Each DP state can be computed in O(n) time (for each possible connection).
    • Total time complexity: O(m * n * 2^n).
    • Space complexity: O(m * 2^n) for memoization.
  • This is feasible for n <= 12 as in Leetcode constraints.

Summary

The problem of finding the minimum cost to connect two groups of points is solved efficiently using dynamic programming with bitmasking. By representing the state as which points in group2 have been connected and building up the solution incrementally, we avoid redundant work and ensure all constraints are met. The key insight is to use bitmask DP to cover all points while minimizing cost, making the approach both elegant and practical for small group sizes.