#1584

Min Cost to Connect All Points

medium· Advanced Graphsruns: 0

You are given an array points representing integer coordinates of some points on a 2D plane. The cost of connecting two points is the Manhattan distance between them. Return the minimum cost to make all points connected, where there is exactly one simple path between any two points.

wpm 0acc 100%time 0:000 / 665

import heapq

class Solution:
    def minCostConnectPoints(
        self, points: list[list[int]]
    ) -> int:
        n = len(points)
        visited = set()
        heap = [(0, 0)]
        total = 0
        while len(visited) < n:
            cost, i = heapq.heappop(heap)
            if i in visited:
                continue
            visited.add(i)
            total += cost
            for j in range(n):
                if j not in visited:
                    dist = abs(points[i][0] - points[j][0]) + abs(
                        points[i][1] - points[j][1]
                    )
                    heapq.heappush(heap, (dist, j))
        return total

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.