Min Cost To Connect All Points Leetcode Problem 1584 [Python Solution]

In this post, we're going to tackle a LeetCode problem, specifically Min Cost To Connect All Points This problem falls under the category of advanced graphs and is categorized as medium difficulty.

We'll explore the problem statement, constraints, and an efficient Python solution using Prim's algorithm.

Problem Overview

Problem Statement:

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the Manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected.

All points are connected if there is exactly one simple path between any two points.

Example:

Let's consider an example to better understand the problem:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20

Explanation:

We can connect the points as shown above to get the minimum cost of 20. Notice that there is a unique path between every pair of points.

Constraints:

• 1 <= points.length <= 1000
• -10^6 <= xi, yi <= 10^6
• All pairs (xi, yi) are distinct.

Now that we have a clear understanding of the problem statement, let's dive into the solution.

Efficient Python Code Solution

We can solve this problem efficiently using Prim's algorithm, which helps find the minimum spanning tree in a graph.

In this case, we'll build a graph where each point is a node, and the distance between two points is an edge's weight.

Here's the Python code to solve the problem:

def minCostConnectPoints(points):
    # Get the number of points
    N = len(points)

    # Create an adjacency list to represent the graph
    adj = {i: [] for i in range(N)}  # i: list of [cost, node]

    # Calculate the distances and populate the adjacency list
    for i in range(N):
        x1, y1 = points[i]
        for j in range(i + 1, N):
            x2, y2 = points[j]
            dist = abs(x1 - x2) + abs(y1 - y2)
            adj[i].append([dist, j])
            adj[j].append([dist, i])

    # Prim's algorithm
    res = 0  # Total cost
    visit = set()  # Set to keep track of visited nodes
    minH = [[0, 0]]  # Min heap to keep track of edges [cost, point]

    while len(visit) < N:
        cost, i = heapq.heappop(minH)  # Pop the minimum cost edge
        if i in visit:
            continue
        res += cost  # Add the cost to the result
        visit.add(i)  # Mark the node as visited

        # Add neighbors to the min heap
        for neiCost, nei in adj[i]:
            if nei not in visit:
                heapq.heappush(minH, [neiCost, nei])

    return res

In this solution, we first build an adjacency list representing the graph, where each node is connected to its neighbors with corresponding edge weights (Manhattan distances).

Then, we use Prim's algorithm to find the minimum spanning tree and calculate the total cost.

Time and Space Complexity

Let's analyze the time and space complexity of our solution:

Time Complexity: O(n^2 * log(n))

• The creation of the adjacency list takes O(n^2) time because we consider all pairs of points.
• The while loop, which applies Prim's algorithm, iterates at most n times (all nodes are visited), and each iteration involves heap operations with a time complexity of log(n).
• So, the overall time complexity is O(n^2 * log(n)).

Space Complexity: O(n^2)

• The adjacency list, adj, consumes O(n^2) space to represent the connections.
• The minH heap also stores at most n elements (the number of nodes).
• Therefore, the space complexity is O(n^2).

Reasoning Behind Our Approach

In this solution, we first create an adjacency list to represent the graph with edges (Manhattan distances) between all pairs of points.

Then, we use Prim's algorithm to find the minimum spanning tree efficiently.

The key idea behind using Prim's algorithm is to start from a node and iteratively add the nearest unvisited node to the tree.

We continue this process until all nodes are visited, ensuring that we have the minimum cost to connect all points.

By building the adjacency list, we optimize the process of finding the nearest neighbors and their corresponding edge weights, making the solution efficient for larger input sizes.

Related Interview Questions By Company:

• Multiply Strings LeetCode
• Interleaving String LeetCode
• Remove All Adjacent Duplicates In String II LeetCode

Related Interview Questions By Difficulty:

• Reconstruct Itinerary LeetCode
• Path With Maximum Probability LeetCode
• Alien Dictionary LeetCode

Conclusion

In this blog post, we addressed the LeetCode problem Min Cost To Connect All Points We provided a detailed problem overview, an efficient Python solution using Prim's algorithm, and an analysis of the time and space complexity.

We hope this explanation helps you understand the problem and the solution.

If you have any questions, suggestions, or feedback, please feel free to comment and share your thoughts.

Happy coding!

For the original problem and more details, you can visit the Min Cost to Connect All Points LeetCode problem.

If you found this post helpful, don't forget to like and engage to support our our platform.

Thanks for watching!