1584. Min Cost to Connect All Points

Medium
Description

給定一組二維平面上的點 points，兩點之間的連接成本為曼哈頓距離 |xi - xj| + |yi - yj|。回傳使所有點連通的最小成本。

Example:

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

Intuition#

最小生成樹 (MST) 問題 – 用 Prim 或 Kruskal 找出連通所有點的最小成本邊集。

  • 所有點兩兩之間都有邊（完全圖），邊權為曼哈頓距離
  • 需要找最小生成樹
  • Prim 適合稠密圖（邊多），Kruskal 適合稀疏圖

Approaches#

1: Kruskal + Union-Find#

  • 概念: 將所有邊按權重排序，依序加入不會形成環的邊，直到加入 n-1 條邊
  • 時間複雜度: O(n^2 log n)（排序 n^2 條邊）
  • 空間複雜度: O(n^2)
class Solution {
    private lateinit var parent: IntArray
    private lateinit var rank: IntArray

    fun minCostConnectPoints(points: Array<IntArray>): Int {
        val n = points.size
        val edges = mutableListOf<IntArray>() // [cost, i, j]

        for (i in 0 until n) {
            for (j in i + 1 until n) {
                val cost = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1])
                edges.add(intArrayOf(cost, i, j))
            }
        }

        edges.sortBy { it[0] }
        parent = IntArray(n) { it }
        rank = IntArray(n)

        var totalCost = 0
        var edgeCount = 0
        for ((cost, u, v) in edges) {
            if (union(u, v)) {
                totalCost += cost
                edgeCount++
                if (edgeCount == n - 1) break
            }
        }
        return totalCost
    }

    private fun find(x: Int): Int {
        if (parent[x] != x) parent[x] = find(parent[x])
        return parent[x]
    }

    private fun union(x: Int, y: Int): Boolean {
        val px = find(x)
        val py = find(y)
        if (px == py) return false
        if (rank[px] < rank[py]) parent[px] = py
        else if (rank[px] > rank[py]) parent[py] = px
        else { parent[py] = px; rank[px]++ }
        return true
    }
}

⭐2: Prim（優先佇列）#

  • 概念: 從任意點開始，每次選擇連接已選集合和未選集合的最小權重邊，貪心擴展 MST
  • 時間複雜度: O(n^2 log n)
  • 空間複雜度: O(n^2)
class Solution {
    fun minCostConnectPoints(points: Array<IntArray>): Int {
        val n = points.size
        val inMST = BooleanArray(n)
        // [cost, pointIndex]
        val pq = PriorityQueue<IntArray>(compareBy { it[0] })
        pq.add(intArrayOf(0, 0))
        var totalCost = 0
        var edgesUsed = 0

        while (edgesUsed < n) {
            val (cost, u) = pq.poll()
            if (inMST[u]) continue
            inMST[u] = true
            totalCost += cost
            edgesUsed++

            for (v in 0 until n) {
                if (!inMST[v]) {
                    val dist = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1])
                    pq.add(intArrayOf(dist, v))
                }
            }
        }
        return totalCost
    }
}
補充解法：Prim（O(n^2) 無 PQ）
  • 概念: 對於完全圖，用陣列記錄每個點到 MST 的最小距離，每次線性掃描找最小值，省去 PQ 開銷
  • 時間複雜度: O(n^2)
  • 空間複雜度: O(n)
class Solution {
    fun minCostConnectPoints(points: Array<IntArray>): Int {
        val n = points.size
        val minDist = IntArray(n) { Int.MAX_VALUE }
        val inMST = BooleanArray(n)
        minDist[0] = 0
        var totalCost = 0

        repeat(n) {
            var u = -1
            for (v in 0 until n) {
                if (!inMST[v] && (u == -1 || minDist[v] < minDist[u])) u = v
            }
            inMST[u] = true
            totalCost += minDist[u]
            for (v in 0 until n) {
                if (!inMST[v]) {
                    val dist = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1])
                    minDist[v] = minOf(minDist[v], dist)
                }
            }
        }
        return totalCost
    }
}

🔑 Takeaways#

  • Pattern: 最小生成樹 – Prim（從頂點擴展）vs Kruskal（按邊排序）
  • 關鍵技巧: 完全圖中 Prim O(n^2) 版本比 PQ 版本更高效；Kruskal 需要先生成所有 O(n^2) 條邊