Min Cost to Connect All Points

Tree
Medium

Approach

Diagrams

Analysis

Time

Space

class Solution:
    def minCostConnectPoints(self, nodes):
        self.nodes = nodes
        self.numNodes = len(nodes)

        edges = self.sortEdgesByWeight()

        minCost = 0

        disjointSet = DisjointSet(self.numNodes)

        for node, otherNode, weight in edges:
            if disjointSet.union(node, otherNode):
                minCost += weight

        return minCost

    def sortEdgesByWeight(self):
        edges = []

        for nodeIdx in range(self.numNodes):
            for otherNodeIdx in range(nodeIdx + 1, self.numNodes):
                weightOfEdge = self.getWeightOfEdge(nodeIdx, otherNodeIdx)
                edges.append((nodeIdx, otherNodeIdx, weightOfEdge))

        edges.sort(key=lambda edge: edge[2])

        return edges

    def getWeightOfEdge(self, nodeIdx, otherNodeIdx):
        node = self.nodes[nodeIdx]
        otherNode = self.nodes[otherNodeIdx]

        nodeX, nodeY = node[0], node[1]
        otherNodeX, otherNodeY = otherNode[0], otherNode[1]

        weightOfEdge = abs(nodeX - otherNodeX) + abs(nodeY - otherNodeY)

        return weightOfEdge


class DisjointSet:
    def __init__(self, numNodes):
        self.roots = [nodeIdx for nodeIdx in range(numNodes)]

    def find(self, node):
        if self.roots[node] != node:
            self.roots[node] = self.find(self.roots[node])

        return self.roots[node]

    def union(self, node, otherNode):
        root = self.find(node)
        otherRoot = self.find(otherNode)

        if root == otherRoot:
            return False

        self.roots[otherRoot] = self.roots[root]
        return True

Learn

#Kruskal's Algorithm

#Union Find

#Minimum Spanning Tree

#Greedy

Videos