15.09.2023
1584. Min Cost to Connect All Points medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/340
Problem TLDR
Min Manhattan distance connected graph
Intuition
We can start from any points, for example, 0
. Next, we must iterate over all possible edges and find one with minimum distance
.
Approach
use
Priority Queue
to sort all edges by distancewe can stop after all nodes are visited once
we can consider only the last edge distance in path
Complexity
Time complexity:
O(n^2)Space complexity:
O(n^2)
Code
fun minCostConnectPoints(points: Array<IntArray>): Int {
fun dist(from: Int, to: Int) =
abs(points[from][0] - points[to][0]) + abs(points[from][1] - points[to][1])
val notVisited = points.indices.toMutableSet()
val pq = PriorityQueue<Pair<Int, Int>>(compareBy({ it.second }))
pq.add(0 to 0)
var sum = 0
while (notVisited.isNotEmpty()) {
val curr = pq.poll()
if (!notVisited.remove(curr.first)) continue
sum += curr.second
for (to in notVisited) pq.add(to to dist(curr.first, to))
}
return sum
}