1584-min-cost-to-connect-all-points

Try it on leetcode

Description

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 1:

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.

Example 2:

Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18

 

Constraints:

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

Solution(Python)

class UnionFind:
    def __init__(self, size):
        self.group = [0] * size
        self.rank = [0] * size

        for i in range(size):
            self.group[i] = i

    def find(self, a):
        if a != self.group[a]:
            self.group[a] = self.find(self.group[a])
        return self.group[a]

    def union(self, a, b):
        groupA = self.find(a)
        groupB = self.find(b)

        if groupA == groupB:
            return False

        if self.rank[groupA] > self.group[groupB]:
            self.group[groupB] = groupA
        elif self.rank[groupB] > self.group[groupA]:
            self.group[groupA] = groupB
        else:
            self.group[groupB] = groupA
            self.rank[groupA] += 1
        return True

    def isconnected(self, a, b):
        return self.find(a) == self.find(b)


class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        return self.optimized_prims(points)

    # Time Complexity: O(n2 log(n))
    # space complexity: o(n^2)
    def kruskar(self, points: List[List[int]]) -> int:
        n = len(points)
        all_edges = []

        for cur_node in range(n):
            for next_node in range(cur_node + 1, n):
                weight = abs(points[cur_node][0] - points[next_node][0]) + abs(
                    points[cur_node][1] - points[next_node][1]
                )
                all_edges.append((weight, cur_node, next_node))
        all_edges.sort()

        uf = UnionFind(n)
        mst_cost = 0
        edges_used = 0

        for w, p1, p2 in all_edges:
            if uf.union(p1, p2):
                mst_cost += w
                edges_used += 1
                if edges_used == n - 1:
                    break

        return mst_cost

    # Time Complexity: O(n2 log(n))
    # space complexity: o(n^2)
    def naiveprims(self, points: List[List[int]]) -> int:
        n = len(points)
        heap = [(0, 0)]

        in_mst = [False] * n

        mst_cost = 0
        edges_used = 0

        while edges_used < n:
            weight, cur_node = heapq.heappop(heap)

            if in_mst[cur_node]:
                continue
            in_mst[cur_node] = True
            mst_cost += weight
            edges_used += 1

            for next_node in range(n):
                if not in_mst[next_node]:
                    next_weight = self.manhattan_dist(
                        points[cur_node], points[next_node]
                    )
                    heapq.heappush(heap, (next_weight, next_node))

        return mst_cost

    def manhattan_dist(self, point1, point2):
        return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])

    # Time Complexity: O(n^2)
    # space complexity: o(n)
    def optimized_prims(self, points: List[List[int]]) -> int:
        n = len(points)
        mst_cost = 0
        edges_used = 0

        in_mst = [False] * n
        min_dist = [math.inf] * n
        min_dist[0] = 0

        while edges_used < n:
            cur_min_edge = math.inf
            cur_node = -1

            for node in range(n):
                if not in_mst[node] and cur_min_edge > min_dist[node]:
                    cur_min_edge = min_dist[node]
                    cur_node = node
            mst_cost += cur_min_edge
            edges_used += 1
            in_mst[cur_node] = True

            for next_node in range(n):
                weight = self.manhattan_dist(
                    points[cur_node], points[next_node])
                if not in_mst[next_node] and min_dist[next_node] > weight:
                    min_dist[next_node] = weight

        return mst_cost