Minimum Cost to Connect Two Groups of Points

Minimum Cost to Connect Two Groups of Points - Problem

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 is given in a 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. In other words, each point in the first group must be connected to at least one point in the second group, and each point in the second group must be connected to at least one point in the first group.

Return the minimum cost it takes to connect the two groups.

Input & Output

Example 1 — Basic Case

$ Input: cost = [[15,96],[36,2]]

› Output: 17

💡 Note: Connect point 0 from group1 to point 0 from group2 (cost=15), and point 1 from group1 to point 1 from group2 (cost=2). Total cost = 15 + 2 = 17. All points are connected.

Example 2 — Multiple Connections

$ Input: cost = [[1,3,5],[4,1,1],[1,5,3]]

› Output: 4

💡 Note: Connect point 0 to point 0 (cost=1), point 1 to point 1 (cost=1), point 2 to point 1 (cost=5). But we can do better: connect point 0 to point 0 (cost=1), point 1 to point 2 (cost=1), point 2 to point 1 (cost=5). However, the optimal is: point 0→0 (cost=1), point 1→1 (cost=1), point 2→2 (cost=3). But point 1 needs connection, so point 1→1 (cost=1), others connect optimally. Answer is 4.

Example 3 — Single Column

$ Input: cost = [[2],[3],[1]]

› Output: 6

💡 Note: Only one point in group2. All three points in group1 must connect to it, so total cost = 2 + 3 + 1 = 6. The single group2 point is connected through all these connections.

Constraints

size1 == cost.length
size2 == cost[i].length
1 ≤ size1, size2 ≤ 12
size1 ≥ size2
0 ≤ cost[i][j] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Two groups with connection costs in matrix format

Constraint

Every point in both groups must be connected to opposite group

Goal

Find minimum cost to satisfy all connection requirements

Key Takeaway

🎯 Key Insight: Use bitmasks to track which points in the smaller group are connected, enabling efficient DP state transitions

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to use dynamic programming with bitmasks to efficiently track which points in the smaller group are connected. The optimal approach uses bottom-up DP with state transitions, achieving O(m × 2^n × n) time complexity. We precompute minimum connection costs and handle unconnected points in the final step.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization	O(m × 2^n × n)	O(m × 2^n)	Use recursion with memoization to avoid recalculating subproblems
Optimized DP with Bottom-Up Approach	O(m × 2^n × n)	O(2^n)	Use iterative DP with bitmasks to find minimum cost efficiently
Brute Force - Try All Connections	O(3^(m×n))	O(m×n)	Generate all possible ways to connect points and find minimum cost

Dynamic Programming with Memoization — Algorithm Steps

Define recursive function with state (index, connected_mask)
For each point in group1, try connecting to each point in group2
Use memoization to cache results for seen states
Handle remaining unconnected group2 points at the end

Visualization

Tap to expand

Step-by-Step Walkthrough

State Representation

Use (point_index, bitmask) to represent which group2 points are connected

Recursive Choices

For each group1 point, try connecting to each group2 point

Memoization

Cache results to avoid recalculating same states

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_STATES 10000

struct MemoEntry {
    int i, mask, value;
} memo[MAX_STATES];
int memoSize = 0;

int minCostGroup2[20];

int findMemo(int i, int mask) {
    for (int k = 0; k < memoSize; k++) {
        if (memo[k].i == i && memo[k].mask == mask) {
            return memo[k].value;
        }
    }
    return -1;
}

void addMemo(int i, int mask, int value) {
    if (memoSize < MAX_STATES) {
        memo[memoSize].i = i;
        memo[memoSize].mask = mask;
        memo[memoSize].value = value;
        memoSize++;
    }
}

int dp(int** cost, int m, int n, int i, int mask) {
    if (i == m) {
        int total = 0;
        for (int j = 0; j < n; j++) {
            if (!(mask & (1 << j))) {
                total += minCostGroup2[j];
            }
        }
        return total;
    }
    
    int cached = findMemo(i, mask);
    if (cached != -1) {
        return cached;
    }
    
    int result = INT_MAX;
    for (int j = 0; j < n; j++) {
        int newMask = mask | (1 << j);
        int current = cost[i][j] + dp(cost, m, n, i + 1, newMask);
        if (current < result) {
            result = current;
        }
    }
    
    addMemo(i, mask, result);
    return result;
}

int solution(int** cost, int m, int n) {
    memoSize = 0;
    
    // Precompute minimum cost to connect each point in group2
    for (int j = 0; j < n; j++) {
        minCostGroup2[j] = INT_MAX;
        for (int i = 0; i < m; i++) {
            if (cost[i][j] < minCostGroup2[j]) {
                minCostGroup2[j] = cost[i][j];
            }
        }
    }
    
    return dp(cost, m, n, 0, 0);
}

int main() {
    // Simple demo
    int result = 0; // Placeholder
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × 2^n × n)

For each of m points, we have 2^n possible states for group2 connections, and n choices per state

⚠ Quadratic Growth

Space Complexity

O(m × 2^n)

Memoization table stores results for each (point, bitmask) combination

⚠ Quadratic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler