Start learning free

LESSON 484 OF 540 · GRAPHS

Min Cost to Connect All Points in Kotlin: Kruskal and 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

    KOTLIN · GRAPHS

    Min Cost To Connect All Points in Kotlin, explained

    Problem overview

    minCostConnectPoints(points) gets an array of [x, y] points. Connecting two points costs their Manhattan distance, |x1 - x2| + |y1 - y2|: the distance along grid lines, like a taxi driving through city blocks. The function returns the least total cost that makes every point reachable from every other by following connections.

    For [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]] the answer is 20: [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. That is four connections for five points, 4 + 3 + 4 + 9 = 20. A single point costs 0.

    Approach

    Treat every pair of points as an edge of a graph, with the Manhattan distance as its cost. You need the cheapest set of edges that connects all the points. That set is a minimum spanning tree: it has exactly n - 1 edges, and any more would close a cycle that only adds cost.

    Kruskal's algorithm builds it greedily:

    1. List all the edges and sort them from the cheapest.
    2. Go through them in that order. If the edge's two points are in different groups, take it: the two groups become one. If they are already in the same group, skip it, since it would close a cycle.
    3. Stop after n - 1 edges, when every point is in one group.

    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 gives a tree that costs no more.

    To ask "are these two points in the same group?" quickly, use union-find: each group is a tree of parent links, and the root, the point that is its own parent, names the group.

    There are n · (n - 1) / 2 edges, and sorting them takes O(n² log n) time, which is fine for up to 1000 points. Prim's algorithm is the other classic way to build the tree, growing it from one point, but this lesson uses Kruskal.

    Step by step

    1. Size. val n = points.size.
    2. The edge list. mutableListOf<IntArray>(). Each edge is an IntArray of cost, i and j, with the cost first because that is what the edges are sorted by.
    3. All pairs. i goes over 0 until n and j over i + 1 until n. Starting at i + 1 lists each pair once and never pairs a point with itself.
    4. Cost and edge. The cost is Math.abs of the x difference plus Math.abs of the y difference. Add intArrayOf(cost, i, j) to edges.
    5. Sort. edges.sortBy { it[0] } sorts the list in place, cheapest first, by the first number of each edge.
    6. Union-find arrays. parent = IntArray(n) { it } makes every point its own root, and size = IntArray(n) { 1 } counts the points in the group of each root.
    7. Totals. var total is the cost so far and var used the number of edges taken.
    8. Go through the edges. For each edge, find rootA of edge[1] and rootB of edge[2] with the helper find. They are vars because they may be swapped.
    9. Different roots? If rootA != rootB, the edge joins two groups. Equal roots mean the points are already connected, and the edge is skipped.
    10. Union by size. If size[rootA] < size[rootB], swap the two roots through temp, so rootA is the root of the larger group. Set parent[rootB] = rootA and add size[rootB] to size[rootA]. Hanging the smaller tree under the larger keeps the trees shallow.
    11. Count it. This is the key line: total += edge[0], since the edge is the cheapest left that joins two groups. Then used++.
    12. Stop early. When used == n - 1, all points are in one group: return total.
    13. After the loop, return total. This is reached only with a single point: no edges, cost 0.
    14. The helper find. It copies node into a var x and, while parent[x] != x, points x to its grandparent and moves up to it. It returns x, the root.

    The solution in Kotlin

    class Solution {
    fun minCostConnectPoints(points: Array<IntArray>): Int {
        val n = points.size
        val edges = mutableListOf<IntArray>()
        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] }
        val parent = IntArray(n) { it }
        val size = IntArray(n) { 1 }
        var total = 0
        var used = 0
        for (edge in edges) {
            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++
                if (used == n - 1) {
                    return total
                }
            }
        }
        return total
    }

    fun find(parent: IntArray, node: Int): Int {
        var x = node
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]
            x = parent[x]
        }
        return x
    }
}

    Kotlin details worth knowing:

    • Lambdas with it. In IntArray(n) { it }, the block runs once per index and it is that index. In edges.sortBy { it[0] }, it is one edge, and the list is sorted by the number the block returns.
    • Parameters are read-only. find cannot change node, so it copies it into the var x.
    • Arrays are passed by reference. When find writes to parent, the caller sees the change. That is how path halving shortens later lookups.
    • Swapping two variables. With a val temp and two assignments, the old rootA is not lost.
    • A loop instead of recursion. find walks up with while, so a long chain cannot overflow the call stack.
    • Math.abs is Java's Math.abs, which Kotlin can call directly. kotlin.math.abs works the same way on an Int.

    Tracing an example

    For [[0, 0], [1, 0], [0, 1], [10, 10]], the edges sorted by cost, each 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 join points 0, 1 and 2: total 2. The edge [2, 1, 2] links two points that are already in one group, so it is skipped. The edge [19, 1, 3] joins the point [10, 10] and makes the total 21. That is the third edge taken, n - 1 = 3, so the function returns 21.

    Complexity

    Time: there are about n² / 2 edges. Building them is O(n²), sorting them is O(n² log n), and the union-find calls cost almost constant time each (the cost grows like the inverse Ackermann function), so the sort dominates: O(n² log n).

    Space: the edge list holds about n² / 2 small arrays, which is O(n²). For 1000 points that is 499,500 edges.

    Edge cases and common mistakes

    • One point. There are no edges, the loop never runs and the function returns 0.
    • Two points. One edge, whose cost is the Manhattan distance: [[0, 0], [3, 4]] gives 7.
    • Negative coordinates. The differences can be negative, so the absolute value is needed: [[3, 12], [-2, 5], [-4, 1]] gives 18.
    • Counting skipped edges. Only add the cost when the roots differ. Adding every cheap edge gives a total that is too high.
    • Using Euclidean distance. The cost is the Manhattan distance, with no square root.
    • Large coordinates. A single difference can be as big as 2,000,000, so one distance is up to 4,000,000, which still fits easily in an Int. For the two points [-1000000, -1000000] and [1000000, 1000000] the answer is 4000000.

    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
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free