1595. Minimum Cost to Connect Two Groups of Points LeetCode Solution
In this guide, you will get 1595. Minimum Cost to Connect Two Groups of Points LeetCode Solution with the best time and space complexity. The solution to Minimum Cost to Connect Two Groups of Points problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Cost to Connect Two Groups of Points
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.
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.
1595. Minimum Cost to Connect Two Groups of Points LeetCode Solution in C++
class Solution {
public:
int connectTwoGroups(vector<vector<int>>& cost) {
const int m = cost.size();
const int n = cost[0].size();
vector<vector<int>> mem(m, vector<int>(1 << n, INT_MAX));
// minCosts[j] := the minimum cost of connecting group2's point j
vector<int> minCosts(n);
for (int j = 0; j < n; ++j) {
int minCostIndex = 0;
for (int i = 1; i < m; ++i)
if (cost[i][j] < cost[minCostIndex][j])
minCostIndex = i;
minCosts[j] = cost[minCostIndex][j];
}
return connectTwoGroups(cost, 0, 0, minCosts, mem);
}
private:
// Returns the minimum cost to connect group1's points[i..n) with group2's
// points, where `mask` is the bitmask of the connected points in group2.
int connectTwoGroups(const vector<vector<int>>& cost, int i, int mask,
const vector<int>& minCosts, vector<vector<int>>& mem) {
if (i == cost.size()) {
// All the points in group 1 are connected, so greedily assign the
// minimum cost for the unconnected points of group2.
int res = 0;
for (int j = 0; j < cost[0].size(); ++j)
if ((mask >> j & 1) == 0)
res += minCosts[j];
return res;
}
if (mem[i][mask] != INT_MAX)
return mem[i][mask];
for (int j = 0; j < cost[0].size(); ++j)
mem[i][mask] =
min(mem[i][mask],
cost[i][j] +
connectTwoGroups(cost, i + 1, mask | 1 << j, minCosts, mem));
return mem[i][mask];
}
}; /* code provided by PROGIEZ */
1595. Minimum Cost to Connect Two Groups of Points LeetCode Solution in Java
class Solution {
public int connectTwoGroups(List<List<Integer>> cost) {
final int m = cost.size();
final int n = cost.get(0).size();
Integer[][] mem = new Integer[m][1 << n];
// minCosts[j] := the minimum cost of connecting group2's point j
int[] minCosts = new int[n];
for (int j = 0; j < n; ++j) {
int minCostIndex = 0;
for (int i = 1; i < m; ++i)
if (cost.get(i).get(j) < cost.get(minCostIndex).get(j))
minCostIndex = i;
minCosts[j] = cost.get(minCostIndex).get(j);
}
return connectTwoGroups(cost, 0, 0, minCosts, mem);
}
// Returns the minimum cost to connect group1's points[i..n) with group2's
// points, where `mask` is the bitmask of the connected points in group2.
private int connectTwoGroups(List<List<Integer>> cost, int i, int mask, int[] minCosts,
Integer[][] mem) {
if (i == cost.size()) {
// All the points in group 1 are connected, so greedily assign the
// minimum cost for the unconnected points of group2.
int res = 0;
for (int j = 0; j < cost.get(0).size(); ++j)
if ((mask >> j & 1) == 0)
res += minCosts[j];
return res;
}
if (mem[i][mask] != null)
return mem[i][mask];
int res = Integer.MAX_VALUE;
for (int j = 0; j < cost.get(0).size(); ++j)
res = Math.min(res, cost.get(i).get(j) +
connectTwoGroups(cost, i + 1, mask | 1 << j, minCosts, mem));
return mem[i][mask] = res;
}
} // code provided by PROGIEZ
1595. Minimum Cost to Connect Two Groups of Points LeetCode Solution in Python
class Solution:
def connectTwoGroups(self, cost: list[list[int]]) -> int:
# minCosts[j] := the minimum cost of connecting group2's point j
minCosts = [min(col) for col in zip(*cost)]
@functools.lru_cache(None)
def dp(i: int, mask: int) -> int:
"""
Returns the minimum cost to connect group1's points[i..n) with group2's
points, where `mask` is the bitmask of the connected points in group2.
"""
if i == len(cost):
# All the points in group 1 are connected, so greedily assign the
# minimum cost for the unconnected points of group2.
return sum(minCost for j, minCost in enumerate(minCosts)
if (mask >> j & 1) == 0)
return min(cost[i][j] + dp(i + 1, mask | 1 << j)
for j in range(len(cost[0])))
return dp(0, 0) # code by PROGIEZ
