LeetCode 1595: Minimum Cost to Connect Two Groups of Points Solution

Master LeetCode problem 1595 (Minimum Cost to Connect Two Groups of Points), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1595. Minimum Cost to Connect Two Groups of Points

Hard

Array Dynamic Programming Bit Manipulation Matrix Bitmask

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming with bitmasking. We will iterate over all possible subsets of points from the first group and find the minimum cost of connecting these points to the points in the second group. We will keep track of the minimum cost for each subset of points in the first group.

Create a dp array of size 2^size1 to store the minimum cost for each subset of points in the first group.
Initialize dp array with maximum cost except for the empty subset (cost 0).
Iterate over all possible subsets of points in the first group.
For each subset, iterate over all points in the second group and find the minimum cost of connecting these points to the subset.
Update the dp array with the minimum cost for each subset.
Finally, return the minimum cost of connecting the two groups.

Time Complexity: O(2^size1 * size2) Space Complexity: O(2^size1)

Solution Code

class Solution {
    public int connectTwoGroups(int[][] cost) {
        int size1 = cost.length;
        int size2 = cost[0].length;
        
        int[][] dp = new int[1 << size1][size2];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        
        for (int mask = 0; mask < (1 << size1); mask++) {
            for (int j = 0; j < size2; j++) {
                for (int i = 0; i < size1; i++) {
                    dp[mask | (1 << i)][j] = Math.min(dp[mask | (1 << i)][j], dp[mask][j] + cost[i][j]);
                    dp[mask][j] = Math.min(dp[mask][j], dp[mask][j] + cost[i][j]);
                }
            }
        }
        
        return dp[(1 << size1) - 1][size2 - 1];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1595 (Minimum Cost to Connect Two Groups of Points)?

This page provides optimized solutions for LeetCode problem 1595 (Minimum Cost to Connect Two Groups of Points) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1595 (Minimum Cost to Connect Two Groups of Points)?

The time complexity for LeetCode 1595 (Minimum Cost to Connect Two Groups of Points) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1595 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1595 in Java, C++, or Python.

Back to LeetCode Solutions