Start learning free

LESSON 484 OF 540 · GRAPHS

Min Cost to Connect All Points in Scala: Kruskal's with Union-Find

Practice O(n2 log n) Read the full explanation

You are given an array points of n points on a grid, where points[i] = [xi, yi].

Connecting two points [xi, yi] and [xj, yj] costs their Manhattan distance, |xi - xj| + |yi - yj|: the distance along the grid lines, the way a taxi drives through city blocks.

Return the minimum total cost to connect all the points. The points are all connected when you can get from any point to any other by following connections.

 

Example 1:

Input: points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]
Output: 20
Explanation: Four connections join the five points for the least total cost:
    [0, 0] - [2, 2] costs 2 + 2 = 4
    [2, 2] - [5, 2] costs 3 + 0 = 3
    [5, 2] - [7, 0] costs 2 + 2 = 4
    [2, 2] - [3, 10] costs 1 + 8 = 9
The total is 4 + 3 + 4 + 9 = 20.

Example 2:

Input: points = [[3, 12], [-2, 5], [-4, 1]]
Output: 18
Explanation: [-2, 5] - [-4, 1] costs 2 + 4 = 6 and [3, 12] - [-2, 5] costs 5 + 7 = 12,
18 in all. Connecting [3, 12] to [-4, 1] instead would cost 7 + 11 = 18 on its own.

Example 3:

Input: points = [[0, 0], [1, 0], [0, 1], [10, 10]]
Output: 21
Explanation: The two cheapest connections are [0, 0] - [1, 0] and [0, 0] - [0, 1], 1 each.
The next cheapest, [1, 0] - [0, 1] (cost 2), joins two points that are already connected
through [0, 0], so it would only add cost. Then [10, 10] joins through [1, 0], at cost
9 + 10 = 19. The total is 1 + 1 + 19 = 21.

 

Constraints:

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

Note:

Your algorithm should run in O(n2 log n) time and use O(n2) extra space.

The tutorial uses Kruskal's algorithm. Think of every pair of points as an edge of a graph, whose cost is the two points' Manhattan distance: there are n · (n - 1) / 2 edges. The cheapest way to connect all the points is a minimum spanning tree: n - 1 edges that connect every point, with the least total cost. Kruskal's algorithm sorts the edges from the cheapest up and takes each edge whose two ends are still in different groups, which joins the two groups into one. An edge whose ends are already in the same group would only close a cycle, so it is skipped. Union-find, as in Number of Connected Components in an Undirected Graph, tells in almost constant time whether two points are in the same group. After n - 1 edges every point is in one group, and the algorithm can stop.

Taking the cheapest edge between two groups is always safe: the finished tree has to join those two groups somehow, and if it used a dearer edge there, swapping in the cheaper one would give a tree that costs no more. Sorting the n2 edges takes O(n2 log n) time, and keeping them takes O(n2) space.

Prim's algorithm is the other classic way: it grows a single tree from one point, each time adding the cheapest edge from the tree to a point outside it, with a heap as in Dijkstra's algorithm or, on a graph where every pair is an edge like this one, with an O(n2) scan.

STEP 1 OF 30
    Ctrl + Enter to check

    SCALA · GRAPHS

    Min Cost To Connect All Points in Scala, explained

    Problem overview

    The method minCostConnectPoints receives an array of points, each an [x, y] pair. Connecting two points costs their Manhattan distance, |xi - xj| + |yi - yj|: the distance along the grid lines. The method returns the minimum total cost of connections that make all the points reachable from one another. The points are distinct, and there are at most 1000 of them.

    In the first example, [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]], four connections join the five points: [0, 0] to [2, 2] costs 4, [2, 2] to [5, 2] costs 3, [5, 2] to [7, 0] costs 4, and [2, 2] to [3, 10] costs 9. The total is 20.

    Approach: Kruskal's algorithm

    Think of every pair of points as an edge of a graph, with the Manhattan distance as its cost. That makes n * (n - 1) / 2 edges, about half a million for 1000 points. The cheapest way to connect all the points is a minimum spanning tree: n - 1 edges that connect every point with the least total cost.

    Kruskal's algorithm builds it greedily. Sort the edges from cheapest up, and take each edge whose two ends are still in different groups, which joins the two groups into one. An edge whose ends are already in the same group would only close a cycle and add cost, so it is skipped. Taking the cheapest edge between two groups is always safe: the finished tree has to join those groups somehow, and swapping in the cheaper edge would give a tree that costs no more.

    To tell quickly whether two points are in the same group, the method uses union-find. Each group is a tree, and each point links to a parent. The root, the one point that is its own parent, names the group. Two points are in the same group exactly when they lead to the same root.

    After n - 1 edges are taken, all points are in one group and the method can stop. Sorting the edges dominates the work: O(n^2 log n) time, and keeping them takes O(n^2) space. Prim's algorithm, which grows one tree from a starting point, is the other classic approach. This lesson uses Kruskal's.

    For the third example, [[0, 0], [1, 0], [0, 1], [10, 10]], the sorted edges, each shown as (cost, i, j), are:

    (1, 0, 1)
(1, 0, 2)
(2, 1, 2)
(19, 1, 3)
(19, 2, 3)
(20, 0, 3)

    The first two edges are taken. The edge (2, 1, 2) joins two points that are already connected through point 0, so it is skipped. Then (19, 1, 3) joins the last point, and with three edges taken the method returns 1 + 1 + 19 = 21.

    Step by step

    1. Store the number of points, points.length, in a val named n.
    2. Create edges as an empty mutable.ArrayBuffer[Array[Int]](). An ArrayBuffer is an array that can grow. Each edge will be Array(cost, i, j), with the cost first because that is what the edges are sorted by.
    3. Loop over i <- 0 until n, and inside it loop over j <- i + 1 until n. Starting at i + 1 lists each pair once and never pairs a point with itself, since connecting i to j costs the same as j to i.
    4. Compute the cost as math.abs of the x difference plus math.abs of the y difference. The absolute value makes each difference a distance whichever point is further left or lower.
    5. Add the edge with edges += Array(cost, i, j).
    6. Sort the edges by cost into sorted with edges.sortBy(_(0)). It returns a sorted copy and leaves edges alone.
    7. Set up union-find. parent is Array.tabulate(n)(i => i), so every point starts as its own root. size is Array.fill(n)(1), where size(r) counts the points in the group with root r.
    8. Keep two counters as vars: total, the cost so far, and used, the number of edges taken. A tree over n points has exactly n - 1 edges.
    9. Loop over the sorted edges with edge <- sorted. edge(0) is the cost, and edge(1) and edge(2) are the two points.
    10. Find both roots with the helper find, into vars rootA and rootB. They are vars because the next step may swap them.
    11. Skip edges inside one group. If rootA != rootB, the edge joins two groups, and the network takes it. Equal roots mean a cycle.
    12. Union by size. If size(rootA) < size(rootB), swap the two roots using a temporary val, so that rootA is the root of the larger group. The smaller tree always goes under the larger one, so no path to a root grows longer than about log2(n) steps.
    13. Merge: set parent(rootB) to rootA, and add size(rootB) to size(rootA).
    14. Take the edge: add edge(0) to total and 1 to used. This is the key line: the edge is the cheapest one left that joins two groups.
    15. Stop early. Once used == n - 1, every point is in one group, so return total right away.
    16. End with total. The loop only reaches this line for a single point: it has no edges, and connecting it costs nothing.
    17. Write the helper find below the main method, inside the class. It takes the parent array and a node and returns the root. Copy node into a var x, since parameters cannot be reassigned.
    18. Climb to the root: while parent(x) != x, set parent(x) to parent(parent(x)) (its grandparent), then set x to parent(x). This is path halving: each node passed skips one level, so later walks from there are shorter. Then return x.

    The solution in Scala

    class Solution {
    def minCostConnectPoints(points: Array[Array[Int]]): Int = {
        val n = points.length
        val edges = mutable.ArrayBuffer[Array[Int]]()
        for (i <- 0 until n) {
            for (j <- i + 1 until n) {
                val cost = math.abs(points(i)(0) - points(j)(0)) + math.abs(points(i)(1) - points(j)(1))
                edges += Array(cost, i, j)
            }
        }
        val sorted = edges.sortBy(_(0))
        val parent = Array.tabulate(n)(i => i)
        val size = Array.fill(n)(1)
        var total = 0
        var used = 0
        for (edge <- sorted) {
            var rootA = find(parent, edge(1))
            var rootB = find(parent, edge(2))
            if (rootA != rootB) {
                if (size(rootA) < size(rootB)) {
                    val temp = rootA
                    rootA = rootB
                    rootB = temp
                }
                parent(rootB) = rootA
                size(rootA) += size(rootB)
                total += edge(0)
                used += 1
                if (used == n - 1) {
                    return total
                }
            }
        }
        total
    }

    def find(parent: Array[Int], node: Int): Int = {
        var x = node
        while (parent(x) != x) {
            parent(x) = parent(parent(x))
            x = parent(x)
        }
        x
    }
}

    The Scala details worth a closer look:

    • Imports. The code uses mutable.ArrayBuffer, which the lesson already makes available. In a file of your own, add import scala.collection.mutable.
    • sortBy(_(0)). _(0) is short for edge => edge(0). sortBy returns a new sorted collection, so the original edges keeps its order. The sort is stable: edges of equal cost stay in the order they were added, which is why (19, 1, 3) comes before (19, 2, 3) above.
    • Array.tabulate and Array.fill. Array.tabulate(n)(f) builds an array whose element i is f(i), so Array.tabulate(4)(i => i) is 0,1,2,3. Array.fill(n)(1) gives n copies of 1.
    • return inside a loop. A for loop over a collection is compiled to a call with a function body, so the return total inside it is a "non-local return". In Scala 3.5 the compiler accepts it, prints the warning Non local returns are no longer supported; use `boundary` and `boundary.break` in `scala.util` instead, and the method still returns correctly. The warning does not stop the build.
    • Parameters are values. find copies node into var x because Scala does not allow assigning to a parameter.
    • Arrays are shared. find receives the same parent array, not a copy, so its path halving changes what the main method sees. That is the point of the compression.
    • The helper is a method, not a nested function. It is declared after its use in the class body. A class's methods can call one another in any order.

    Complexity

    Let n be the number of points.

    Time: O(n^2 log n). Building the edges is O(n^2), and sorting about n^2 / 2 of them is O(n^2 log n). The union-find calls cost almost nothing each: with union by size and path halving, a find takes nearly constant time on average.

    Space: O(n^2). The edge list holds n * (n - 1) / 2 arrays of three integers, and the sorted copy holds the same again. The two union-find arrays take O(n).

    Edge cases and common mistakes

    • A single point. [[5, 5]] has no edges, used == n - 1 is never checked, and the method returns total, 0.
    • Two points. [[0, 0], [3, 4]] gives 7, the Manhattan distance: 3 + 4. It is not 5, the straight-line distance.
    • Negative coordinates. [[3, 12], [-2, 5], [-4, 1]] gives 18. math.abs takes care of the signs. Far-apart points are fine too: [[-1000000, -1000000], [1000000, 1000000]] gives 4000000.
    • Points on a diagonal. [[0, 0], [1, 1], [2, 2]] gives 4: two connections of cost 2 each. The direct connection from the first to the last would cost 4 by itself.
    • Taking every cheap edge. Skipping the root check adds edges that close cycles, such as (2, 1, 2) in the third example, and the total comes out too high.
    • Not hanging one root under the other. If the merge step is left out, the groups never combine, and every edge looks like it joins separate groups.
    • Using j <- 0 until n. That lists each pair twice and also pairs each point with itself, at cost 0. Starting at i + 1 avoids both.

    Testing

    • [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]] gives 20.
    • [[3, 12], [-2, 5], [-4, 1]] gives 18.
    • [[0, 0], [1, 0], [0, 1], [10, 10]] gives 21.
    • [[5, 5]] gives 0.
    • [[0, 0], [3, 4]] gives 7.
    • [[0, 0], [1, 1], [2, 2]] gives 4.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free