# Minimum Cost to Connect Two Groups of Points

This page explains Java solution to problem `Minimum Cost to Connect Two Groups of Points` using `Bit Masking`.

## Problem Statement

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

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class MinimumCostToConnectTwoGroupsOfPoints {
public int connectTwoGroups(List<List<Integer>> cost) {
int size1 = cost.size();
int size2 = cost.get(0).size();

int[] dp = new int[(1 << size2)];
Arrays.fill(dp, Integer.MAX_VALUE);
dp = 0;

//Iterate over all the elements from group1
for(int group1 = 0; group1 < size1; group1++) {
int[] current = new int[(1 << size2)];
Arrays.fill(current, Integer.MAX_VALUE);

//For each element in a group1 there are 2^group2 possibilities
//Because each element from group1 can connect to one or more element from group2
for(int group2 = 0; group2 < size2; group2++) {

//Iterate over all 2^group2 possibilities

//If group2 element is not connected in a current mask,
if((mask & (1 << group2)) == 0) {
}
}

//Check if newMask value can be reduced further by using previous row state
}
}
}
dp = current;
}

return dp[(1 << size2) - 1];
}
}
``````

## Time Complexity

O(NM * 2M) Where
N is number of elements in a group1
M is number of elements in a group2

## Space Complexity

O(2M) Where
M is number of elements in a group2