LeetCode 1595 - Minimum Cost to Connect Two Groups of Points

The problem is asking us to find the minimum cost to connect two groups of points, where the first group has size1 point

leetcodehardarraydynamic-programmingbit-manipulationmatrixbitmask

LeetCode Problem 1595

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation, Matrix, Bitmask

Solution

Problem Understanding

The problem is asking us to find the minimum cost to connect two groups of points, where the first group has size1 points and the second group has size2 points. We are given a cost matrix cost of size size1 x size2 where cost[i][j] represents the cost of connecting the i-th point in the first group to the j-th point in the second group.

A valid connection means every point in the first group is connected to at least one point in the second group, and every point in the second group is connected to at least one point in the first group. Connections can be multiple for a single point, so there is no restriction on connecting one point to multiple points in the other group. The goal is to find the configuration of connections that minimizes the total cost.

The constraints are small enough for dynamic programming: size1 and size2 are at most 12, which suggests bitmask DP is feasible since 2^12 = 4096. size1 >= size2 tells us we can iterate efficiently over the smaller group's subsets. The cost[i][j] values range from 0 to 100, which is manageable for summing.

Important edge cases include when size1 or size2 is 1, when all costs are equal, and when some costs are 0. These cases could affect the correctness of a naive greedy solution.

Approaches

The brute-force approach would be to generate all possible ways to connect points from the first group to the second group such that all points are connected. For each configuration, we sum the costs and select the minimum. This is correct but infeasible because the number of combinations grows exponentially: each point in the first group has 2^size2 - 1 valid ways to connect to the second group, leading to (2^size2 - 1)^size1 total combinations, which is astronomically large even for size1 = 12 and size2 = 12.

The optimal approach uses dynamic programming with bitmasks to represent subsets of the second group that have already been connected. We iterate over each point in the first group and consider connecting it to all possible subsets of the second group, updating a DP table to track the minimum cost for each subset of connections. The key insight is that we can represent the connected state of the second group as a bitmask, allowing us to efficiently store and update states while considering all combinations.

Approach Time Complexity Space Complexity Notes
Brute Force O((2^size2 - 1)^size1) O(1) Enumerates all valid connection subsets, impractical for max constraints
Optimal O(size1 * 2^size2 * size2) O(2^size2) Uses DP with bitmask over subsets of second group, feasible for size <= 12

Algorithm Walkthrough

  1. Initialize a DP array of size 2^size2 representing all possible subsets of connected points in the second group. Each element dp[mask] will store the minimum cost to connect points in the first group processed so far to the subset represented by mask. Initially, dp[0] = 0 and all others are infinity.
  2. Iterate over each point i in the first group. For each i, initialize a new DP array new_dp to store updated costs. We will compute the minimum cost for each subset of connected points after including point i.
  3. For each subset mask of the second group, check all points j in the second group. For each j, calculate the new mask mask | (1 << j) representing the union of the current subset and connecting i to j. Update new_dp[new_mask] as the minimum of its current value and dp[mask] + cost[i][j].
  4. After processing all points in the second group for i, assign dp = new_dp.
  5. After processing all points in the first group, the minimum cost to connect both groups completely is dp[(1 << size2) - 1], which represents all points in the second group connected.

Why it works: The DP invariant is that dp[mask] always represents the minimum cost to connect the first i points to the subset of the second group represented by mask. By iteratively updating subsets with each point from the first group, we ensure that all connection combinations are considered efficiently without redundant recalculation.

Python Solution

from typing import List

class Solution:
    def connectTwoGroups(self, cost: List[List[int]]) -> int:
        size1, size2 = len(cost), len(cost[0])
        max_mask = 1 << size2
        dp = [float('inf')] * max_mask
        dp[0] = 0
        
        for i in range(size1):
            new_dp = [float('inf')] * max_mask
            for mask in range(max_mask):
                if dp[mask] == float('inf'):
                    continue
                for j in range(size2):
                    new_mask = mask | (1 << j)
                    new_dp[new_mask] = min(new_dp[new_mask], dp[mask] + cost[i][j])
            dp = new_dp
        
        return dp[max_mask - 1]

The code initializes a DP array for all possible subsets of the second group. For each point in the first group, it updates the DP array considering connections to each point in the second group. After all points are processed, the last element dp[max_mask - 1] gives the minimum cost for connecting all points in both groups.

Go Solution

import "math"

func connectTwoGroups(cost [][]int) int {
    size1, size2 := len(cost), len(cost[0])
    maxMask := 1 << size2
    dp := make([]int, maxMask)
    for i := 1; i < maxMask; i++ {
        dp[i] = math.MaxInt32
    }

    for i := 0; i < size1; i++ {
        newDP := make([]int, maxMask)
        for k := range newDP {
            newDP[k] = math.MaxInt32
        }
        for mask := 0; mask < maxMask; mask++ {
            if dp[mask] == math.MaxInt32 {
                continue
            }
            for j := 0; j < size2; j++ {
                newMask := mask | (1 << j)
                if dp[mask]+cost[i][j] < newDP[newMask] {
                    newDP[newMask] = dp[mask] + cost[i][j]
                }
            }
        }
        dp = newDP
    }

    return dp[maxMask-1]
}

The Go implementation follows the same logic as Python but uses math.MaxInt32 to represent infinity. Slices are used for the DP array, and we ensure that each subset update checks for a lower cost before assignment.

Worked Examples

Example 1:

cost = [[15, 96], [36, 2]]

Initial dp = [0, inf, inf, inf]

Processing first point i = 0:

  • Connect to j=0 -> new_mask=1, new_dp[1] = 0+15=15
  • Connect to j=1 -> new_mask=2, new_dp[2] = 0+96=96

Processing second point i = 1:

  • For mask=1, connect to j=0 -> new_mask=1, new_dp[1] = 15+36=51, connect to j=1 -> new_mask=3, new_dp[3]=15+2=17
  • For mask=2, connect to j=0 -> new_mask=3, new_dp[3]=min(17, 96+36=132)=17, connect to j=1 -> new_mask=2, new_dp[2]=96+2=98

Final dp = [inf, 51, 98, 17] → answer = 17

Complexity Analysis

Measure Complexity Explanation
Time O(size1 * 2^size2 * size2) For each of the size1 points, we iterate over 2^size2 masks and size2 connections
Space O(2^size2) Only two DP arrays of size 2^size2 are maintained

The complexity is feasible given the constraints size1, size2 <= 12, making 2^12 = 4096, which is manageable.

Test Cases

# Example tests
assert Solution().connectTwoGroups([[15, 96], [36, 2]]) == 17  # small 2x2 matrix
assert Solution().connectTwoGroups([[1,3,5],[4,1,1],[1,5,3]]) == 4  # 3x3 matrix
assert Solution().connectTwoGroups([[2,5,1],[3,4,7],[8,1,2],[6,2,4],[3,8,8]]) == 10  # 5x3 matrix

# Edge tests
assert Solution().connectTwoGroups([[0]]) == 0  # single point, zero cost
assert Solution().connectTwoGroups([[1]]) == 1  # single point, non-zero cost
assert Solution().connectTwoGroups([[1,