We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Connect Two Groups of Points

Number: 1717

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given two groups of points, where the cost of connecting a point in the first group to a point in the second group is provided in a matrix, find the minimum total cost such that every point in both groups is connected to at least one point in the opposite group.

Key Insights

  • Use dynamic programming with bitmasking to represent the state of connections for the second group.
  • The state dp[i][mask] represents the minimum cost after processing the first i points and having the set of connected points in the second group as given by the bitmask.
  • For every point in the first group, try connecting it to every point in the second group, and update the state.
  • After matching all points from the first group, any unconnected point in the second group should be connected using its minimal connection cost from any point in the first group.

Space and Time Complexity

Time Complexity: O(m * 2^n * n) where m is the number of points in the first group and n is the number of points in the second group. Space Complexity: O(m * 2^n) to store the DP table.

Solution

We solve the problem by using bitmask dynamic programming. Let m be the number of points in the first group and n be the number in the second group. We maintain a DP table dp[i][mask] indicating the minimum cost after processing the first i points from group one with a connectivity state 'mask' for the second group (where each bit of mask indicates if a corresponding point in group two has been connected).

For every point in the first group, iterate through each state of the bitmask. For each possible connection (to any point j in group two), update the new mask by setting bit j. The best cost is updated by comparing the previous state cost plus cost[i][j]. Once all points from the first group are processed, if any point in the second group remains unconnected in the final state, we add the minimum cost needed to connect that point from any point in the first group (this can be precomputed for all j).

This approach efficiently covers all combinations of connections using a bitmask state and ensures that every point is connected with minimum cost.

Code Solutions

Below are the code solutions in Python, JavaScript, C++, and Java. Each solution uses clear variable names and includes line-by-line comments.

import math

class Solution:
    def connectTwoGroups(self, cost):
        m = len(cost)             # number of points in group one
        n = len(cost[0])          # number of points in group two
        # Initialize DP table with infinity; dimensions: (m+1) x (1<<n)
        dp = [[math.inf] * (1 << n) for _ in range(m + 1)]
        dp[0][0] = 0              # No cost to start with no points processed and no connections
        
        # Precompute the minimum cost to connect any point in group one to each point in group two
        min_cost_for_point = [min(cost[i][j] for i in range(m)) for j in range(n)]
        
        # Iterate over each point in group one
        for i in range(m):
            # Iterate over each mask state of connected points in group two
            for mask in range(1 << n):
                if dp[i][mask] == math.inf:
                    continue
                # For the current point, try connecting to every point in group two
                for j in range(n):
                    new_mask = mask | (1 << j)  # Set the bit corresponding to point j
                    dp[i + 1][new_mask] = min(dp[i + 1][new_mask],
                                              dp[i][mask] + cost[i][j])
        # After processing all points in group one, ensure all points in group two are connected.
        # For any mask that is not complete (i.e. not all points connected), add the minimal extra cost.
        result = math.inf
        full_mask = (1 << n) - 1
        for mask in range(1 << n):
            if dp[m][mask] == math.inf:
                continue
            extra_cost = 0
            # For each point in group two not connected yet, add its minimum connection cost.
            for j in range(n):
                if (mask >> j) & 1 == 0:
                    extra_cost += min_cost_for_point[j]
            result = min(result, dp[m][mask] + extra_cost)
        return result
← Back to All Questions