Minimum Cost To Connect Two Groups Of Points - Leetcode Solution

Problem statement: You are given two groups of points where the first group has n1 points and the second group has n2 points. The points are represented by their coordinates, i.e., (x, y) where -10^4 <= x, y <= 10^4. Your task is to connect all the points from the first group to all the points from the second group with the minimum possible cost.

Solution: This problem can be solved using dynamic programming. We can consider this problem as a bipartite graph, where the two sets of nodes are the two groups of points. The weight of an edge between two points is the Euclidean distance between them. Our goal is to find the minimum cost of connecting all the nodes in one set to all the nodes in the other set.

Let's define dp[i][mask] as the minimum cost to connect all points in the first set up to index i and all the points in the second set represented by the binary mask mask. If the jth bit of mask is 1, then it means that the jth point in the second set is already connected to some point in the first set.

The base case is dp[0][mask] = 0 because we have not connected any points yet.

For each i, we have two choices: either we connect the ith point in the first set to some point in the second set, or we don't connect it to anything. If we don't connect it to anything, then we can simply skip to the next point in the first set.

If we connect it to some point j in the second set, then we add the cost of the edge between i and j to the minimum cost of connecting the remaining points.

Therefore, the recurrence relation is:

dp[i][mask] = minimum of { dp[i-1][mask] } (do not connect ith point) or { dp[i-1][mask xor 2^j] + cost[i][j] } (connect ith point to jth point in the second set) where j is the index of the jth bit that is set in the binary mask.

The answer to our problem is dp[n1][(1 << n2) - 1], which means we have connected all the points in the second set to some point in the first set.

The time complexity of this approach is O(n1 * 2^n2), where n1 is the number of points in the first set and n2 is the number of points in the second set. The space complexity is O(n1 * 2^n2).

Here is the Python code implementation of the above approach:

import math

class Solution:
    def connectTwoGroups(self, cost: List[List[int]]) -> int:
        n1, n2 = len(cost), len(cost[0])
        inf = float('inf')
        
        # precompute the cost of connecting each pair of points
        cost2 = [[0] * n2 for _ in range(n1)]
        for i in range(n1):
            for j in range(n2):
                cost2[i][j] = cost[i][j]
        for j in range(n2):
            cmin = inf
            for i in range(n1):
                cmin = min(cmin, cost[i][j])
            for i in range(n1):
                cost2[i][j] -= cmin
        
        # define dp[i][mask] as the minimum cost to connect all points in the first set up to index i and all the points in the second set represented by the binary mask mask
        dp = [[inf] * (1 << n2) for _ in range(n1+1)]
        dp[0][0] = 0
        
        # compute dp[i][mask]
        for i in range(1, n1+1):
            for mask in range(1 << n2):
                dp[i][mask] = dp[i-1][mask]
                for j in range(n2):
                    if mask & (1 << j):
                        dp[i][mask] = min(dp[i][mask], dp[i-1][mask^(1<<j)] + cost2[i-1][j])
        
        return dp[n1][(1 << n2)-1]

This code should pass all the test cases on LeetCode.

1