Skip to content

1595. Minimum Cost to Connect Two Groups of Points

Description

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 are given in an 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.

Β 

Example 1:

Input: cost = [[15, 96], [36, 2]]
Output: 17
Explanation: The optimal way of connecting the groups is:
1--A
2--B
This results in a total cost of 17.

Example 2:

Input: cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
Output: 4
Explanation: The optimal way of connecting the groups is:
1--A
2--B
2--C
3--A
This results in a total cost of 4.
Note that there are multiple points connected to point 2 in the first group and point A in the second group. This does not matter as there is no limit to the number of points that can be connected. We only care about the minimum total cost.

Example 3:

Input: cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
Output: 10

Β 

Constraints:

  • size1 == cost.length
  • size2 == cost[i].length
  • 1 <= size1, size2 <= 12
  • size1 >= size2
  • 0 <= cost[i][j] <= 100

Solutions

Solution 1: Bitmask Dynamic Programming

Let \(m\) and \(n\) denote the number of points in the first group and the second group, respectively.

Since \(1 \leq n \leq m \leq 12\), we can use an integer to represent the state of points in the second group β€” specifically, a binary integer of length \(n\), where bit \(k\) being \(1\) means the \(k\)-th point in the second group is connected to some point in the first group, and \(0\) means it is not.

Next, we define \(f[i][j]\) as the minimum cost when the first \(i\) points in the first group are all connected, and the state of points in the second group is \(j\). Initially, \(f[0][0] = 0\) and all other values are positive infinity. The answer is \(f[m][2^n - 1]\).

Consider \(f[i][j]\) where \(i \geq 1\). We enumerate each point \(k\) in the second group. If point \(k\) is connected to the \(i\)-th point in the first group, we discuss the following two cases:

  • If point \(k\) is only connected to the \(i\)-th point in the first group, then \(f[i][j]\) can be transitioned from \(f[i][j \oplus 2^k]\) or \(f[i - 1][j \oplus 2^k]\), where \(\oplus\) denotes the XOR operation;
  • If point \(k\) is connected to the \(i\)-th point in the first group as well as other points, then \(f[i][j]\) can be transitioned from \(f[i - 1][j]\).

In both cases, we take the minimum transition value:

\[ f[i][j] = \min_{k \in \{0, 1, \cdots, n - 1\}} \{f[i][j \oplus 2^k], f[i - 1][j \oplus 2^k], f[i - 1][j]\} + cost[i - 1][k] \]

Finally, we return \(f[m][2^n - 1]\).

The time complexity is \(O(m \times n \times 2^n)\) and the space complexity is \(O(m \times 2^n)\), where \(m\) and \(n\) are the number of points in the first group and the second group, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def connectTwoGroups(self, cost: List[List[int]]) -> int:
        m, n = len(cost), len(cost[0])
        f = [[inf] * (1 << n) for _ in range(m + 1)]
        f[0][0] = 0
        for i in range(1, m + 1):
            for j in range(1 << n):
                for k in range(n):
                    if (j >> k & 1) == 0:
                        continue
                    c = cost[i - 1][k]
                    x = min(f[i][j ^ (1 << k)], f[i - 1][j], f[i - 1][j ^ (1 << k)]) + c
                    f[i][j] = min(f[i][j], x)
        return f[m][-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int connectTwoGroups(List<List<Integer>> cost) {
        int m = cost.size(), n = cost.get(0).size();
        final int inf = 1 << 30;
        int[][] f = new int[m + 1][1 << n];
        for (int[] g : f) {
            Arrays.fill(g, inf);
        }
        f[0][0] = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 0; j < 1 << n; ++j) {
                for (int k = 0; k < n; ++k) {
                    if ((j >> k & 1) == 1) {
                        int c = cost.get(i - 1).get(k);
                        f[i][j] = Math.min(f[i][j], f[i][j ^ (1 << k)] + c);
                        f[i][j] = Math.min(f[i][j], f[i - 1][j] + c);
                        f[i][j] = Math.min(f[i][j], f[i - 1][j ^ (1 << k)] + c);
                    }
                }
            }
        }
        return f[m][(1 << n) - 1];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int connectTwoGroups(vector<vector<int>>& cost) {
        int m = cost.size(), n = cost[0].size();
        int f[m + 1][1 << n];
        memset(f, 0x3f, sizeof(f));
        f[0][0] = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 0; j < 1 << n; ++j) {
                for (int k = 0; k < n; ++k) {
                    if (j >> k & 1) {
                        int c = cost[i - 1][k];
                        int x = min({f[i][j ^ (1 << k)], f[i - 1][j], f[i - 1][j ^ (1 << k)]}) + c;
                        f[i][j] = min(f[i][j], x);
                    }
                }
            }
        }
        return f[m][(1 << n) - 1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func connectTwoGroups(cost [][]int) int {
    m, n := len(cost), len(cost[0])
    const inf = 1 << 30
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, 1<<n)
        for j := range f[i] {
            f[i][j] = inf
        }
    }
    f[0][0] = 0
    for i := 1; i <= m; i++ {
        for j := 0; j < 1<<n; j++ {
            for k := 0; k < n; k++ {
                c := cost[i-1][k]
                if j>>k&1 == 1 {
                    f[i][j] = min(f[i][j], f[i][j^(1<<k)]+c)
                    f[i][j] = min(f[i][j], f[i-1][j]+c)
                    f[i][j] = min(f[i][j], f[i-1][j^(1<<k)]+c)
                }
            }
        }
    }
    return f[m][(1<<n)-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function connectTwoGroups(cost: number[][]): number {
    const m = cost.length;
    const n = cost[0].length;
    const inf = 1 << 30;
    const f = Array.from({ length: m + 1 }, () => Array(1 << n).fill(inf));
    f[0][0] = 0;
    for (let i = 1; i <= m; ++i) {
        for (let j = 0; j < 1 << n; ++j) {
            for (let k = 0; k < n; ++k) {
                if (((j >> k) & 1) === 1) {
                    const c = cost[i - 1][k];
                    f[i][j] = Math.min(f[i][j], f[i][j ^ (1 << k)] + c);
                    f[i][j] = Math.min(f[i][j], f[i - 1][j] + c);
                    f[i][j] = Math.min(f[i][j], f[i - 1][j ^ (1 << k)] + c);
                }
            }
        }
    }
    return f[m][(1 << n) - 1];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
impl Solution {
    pub fn connect_two_groups(cost: Vec<Vec<i32>>) -> i32 {
        let m = cost.len();
        let n = cost[0].len();
        let inf = 1 << 30;

        let mut f = vec![vec![inf; 1 << n]; m + 1];
        f[0][0] = 0;

        for i in 1..=m {
            for j in 0..(1 << n) {
                for k in 0..n {
                    if (j >> k) & 1 == 1 {
                        let c = cost[i - 1][k];
                        f[i][j] = f[i][j].min(f[i][j ^ (1 << k)] + c);
                        f[i][j] = f[i][j].min(f[i - 1][j] + c);
                        f[i][j] = f[i][j].min(f[i - 1][j ^ (1 << k)] + c);
                    }
                }
            }
        }

        f[m][(1 << n) - 1]
    }
}

Solution 2: Bitmask Dynamic Programming (Space Optimization)

We notice that the transition of \(f[i][j]\) only depends on \(f[i - 1][\cdot]\) and \(f[i][\cdot]\), so we can use a rolling array to optimize the space complexity down to \(O(2^n)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def connectTwoGroups(self, cost: List[List[int]]) -> int:
        m, n = len(cost), len(cost[0])
        f = [inf] * (1 << n)
        f[0] = 0
        g = f[:]
        for i in range(1, m + 1):
            for j in range(1 << n):
                g[j] = inf
                for k in range(n):
                    if (j >> k & 1) == 0:
                        continue
                    c = cost[i - 1][k]
                    x = min(g[j ^ (1 << k)], f[j], f[j ^ (1 << k)]) + c
                    g[j] = min(g[j], x)
            f = g[:]
        return f[-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int connectTwoGroups(List<List<Integer>> cost) {
        int m = cost.size(), n = cost.get(0).size();
        final int inf = 1 << 30;
        int[] f = new int[1 << n];
        Arrays.fill(f, inf);
        f[0] = 0;
        int[] g = f.clone();
        for (int i = 1; i <= m; ++i) {
            for (int j = 0; j < 1 << n; ++j) {
                g[j] = inf;
                for (int k = 0; k < n; ++k) {
                    if ((j >> k & 1) == 1) {
                        int c = cost.get(i - 1).get(k);
                        g[j] = Math.min(g[j], g[j ^ (1 << k)] + c);
                        g[j] = Math.min(g[j], f[j] + c);
                        g[j] = Math.min(g[j], f[j ^ (1 << k)] + c);
                    }
                }
            }
            System.arraycopy(g, 0, f, 0, 1 << n);
        }
        return f[(1 << n) - 1];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int connectTwoGroups(vector<vector<int>>& cost) {
        int m = cost.size(), n = cost[0].size();
        const int inf = 1 << 30;
        vector<int> f(1 << n, inf);
        f[0] = 0;
        vector<int> g = f;
        for (int i = 1; i <= m; ++i) {
            for (int j = 0; j < 1 << n; ++j) {
                g[j] = inf;
                for (int k = 0; k < n; ++k) {
                    if (j >> k & 1) {
                        int c = cost[i - 1][k];
                        int x = min({g[j ^ (1 << k)], f[j], f[j ^ (1 << k)]}) + c;
                        g[j] = min(g[j], x);
                    }
                }
            }
            f.swap(g);
        }
        return f[(1 << n) - 1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func connectTwoGroups(cost [][]int) int {
    m, n := len(cost), len(cost[0])
    const inf = 1 << 30
    f := make([]int, 1<<n)
    for i := range f {
        f[i] = inf
    }
    f[0] = 0
    g := make([]int, 1<<n)
    for i := 1; i <= m; i++ {
        for j := 0; j < 1<<n; j++ {
            g[j] = inf
            for k := 0; k < n; k++ {
                c := cost[i-1][k]
                if j>>k&1 == 1 {
                    g[j] = min(g[j], g[j^1<<k]+c)
                    g[j] = min(g[j], f[j]+c)
                    g[j] = min(g[j], f[j^1<<k]+c)
                }
            }
        }
        copy(f, g)
    }
    return f[1<<n-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function connectTwoGroups(cost: number[][]): number {
    const m = cost.length;
    const n = cost[0].length;
    const inf = 1 << 30;
    const f: number[] = new Array(1 << n).fill(inf);
    f[0] = 0;
    const g = new Array(1 << n).fill(0);
    for (let i = 1; i <= m; ++i) {
        for (let j = 0; j < 1 << n; ++j) {
            g[j] = inf;
            for (let k = 0; k < n; ++k) {
                if (((j >> k) & 1) === 1) {
                    const c = cost[i - 1][k];
                    g[j] = Math.min(g[j], g[j ^ (1 << k)] + c);
                    g[j] = Math.min(g[j], f[j] + c);
                    g[j] = Math.min(g[j], f[j ^ (1 << k)] + c);
                }
            }
        }
        f.splice(0, f.length, ...g);
    }
    return f[(1 << n) - 1];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
impl Solution {
    pub fn connect_two_groups(cost: Vec<Vec<i32>>) -> i32 {
        let m = cost.len();
        let n = cost[0].len();
        let inf = 1 << 30;

        let mut f = vec![inf; 1 << n];
        f[0] = 0;

        let mut g = f.clone();

        for i in 1..=m {
            for j in 0..(1 << n) {
                g[j] = inf;
                for k in 0..n {
                    if (j >> k) & 1 == 1 {
                        let c = cost[i - 1][k];
                        g[j] = g[j].min(g[j ^ (1 << k)] + c);
                        g[j] = g[j].min(f[j] + c);
                        g[j] = g[j].min(f[j ^ (1 << k)] + c);
                    }
                }
            }
            f.clone_from_slice(&g);
        }

        f[(1 << n) - 1]
    }
}

Comments