Start learning free

LESSON 483 OF 539 · GRAPHS

Min Cost to Connect All Points in C#: 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

    C# · GRAPHS

    Min Cost To Connect All Points in C#, explained

    Problem overview

    The method MinCostConnectPoints receives points, a jagged array of [x, y] pairs. Connecting two points costs their Manhattan distance, |x1 - x2| + |y1 - y2|: the distance along grid lines. The method returns the least total cost that connects all the points, meaning you can get from any point to any other by following connections. There are between 1 and 1000 distinct points, with coordinates up to a million in absolute value.

    In the first example, {{0,0},{2,2},{3,10},{5,2},{7,0}}, four connections are enough: (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, so the answer is 20. In the third example, {{0,0},{1,0},{0,1},{10,10}}, the answer is 21: two connections of cost 1 and one of cost 19. A connection between (1,0) and (0,1) costs 2 but would only link two points that are already linked through (0,0).

    The lesson asks for O(n² log n) time and O(n²) extra space.

    Approach: Kruskal's algorithm

    Treat every pair of points as an edge of a graph, with the Manhattan distance as its cost. That makes n · (n - 1) / 2 edges. The cheapest way to connect everything is a minimum spanning tree: n - 1 edges that join every point, with the lowest total cost. Fewer edges can't connect n points, and more would close a cycle that only adds cost.

    Kruskal's algorithm sorts the edges from cheapest to dearest and takes each edge whose two ends are still in different groups, merging the groups. An edge whose ends are already in the same group is skipped. Taking the cheapest edge between two groups is always safe: the finished tree has to join those groups somehow, and swapping a dearer edge for the cheaper one never raises the total.

    The question "are these two points in the same group?" is answered by union-find. Each group is a tree of parent links, and 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, every point is in one group and the algorithm can stop.

    Sorting about n²/2 edges takes O(n² log n), and keeping them takes O(n²) space. Prim's algorithm is another classic approach, growing one tree from a single point. This lesson uses Kruskal's.

    Step by step

    1. Store points.Length in n.
    2. Create edges, a List<int[]>. Each edge is an array { cost, i, j }, with the cost first because that is what the edges are sorted by.
    3. Loop over every pair. The outer loop runs i from 0 to n - 1 and the inner one runs j from i + 1. Starting at i + 1 lists each pair once and never pairs a point with itself.
    4. Compute the cost as Math.Abs of the x difference plus Math.Abs of the y difference, and add the edge to the list.
    5. Sort the edges with edges.Sort and a lambda that returns first[0] - second[0]. A negative result puts the first edge in front. Costs are at most 4,000,000, so the subtraction can't overflow.
    6. Set up union-find. Create parent and size, both int arrays of length n. Then loop over the points and set parent[i] to i (every point is its own root) and size[i] to 1.
    7. Create total and used, both 0: the cost so far and the number of edges taken.
    8. Loop over edges, cheapest first. Find the roots of edge[1] and edge[2] with Find, which is written at the end, and store them in rootA and rootB.
    9. If the roots differ, the edge joins two groups. Make rootA the root of the larger group by swapping the two with a tuple assignment when size[rootA] < size[rootB]. This is union by size.
    10. Merge: set parent[rootB] to rootA, add size[rootB] to size[rootA], add edge[0] to total and add one to used.
    11. Stop early. When used == n - 1, return total. The remaining edges could only close cycles.
    12. Return total after the loop. With a single point there are no edges, and the cost is 0. With two or more points the loop always returns from inside, since every pair is an edge.
    13. Write Find. While parent[x] != x, set parent[x] to parent[parent[x]] and then x to parent[x]. Return x.

    The solution in C#

    class Solution {
    public int MinCostConnectPoints(int[][] points) {
        int n = points.Length;
        List<int[]> edges = new List<int[]>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int cost = Math.Abs(points[i][0] - points[j][0]) + Math.Abs(points[i][1] - points[j][1]);
                edges.Add(new int[] { cost, i, j });
            }
        }
        edges.Sort((first, second) => first[0] - second[0]);
        int[] parent = new int[n];
        int[] size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        int total = 0;
        int used = 0;
        foreach (int[] edge in edges) {
            int rootA = Find(parent, edge[1]);
            int rootB = Find(parent, edge[2]);
            if (rootA != rootB) {
                if (size[rootA] < size[rootB]) {
                    (rootA, rootB) = (rootB, rootA);
                }
                parent[rootB] = rootA;
                size[rootA] += size[rootB];
                total += edge[0];
                used++;
                if (used == n - 1) {
                    return total;
                }
            }
        }
        return total;
    }

    public int Find(int[] parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}

    The C# details worth knowing:

    • Sorting with a lambda. List<T>.Sort accepts a comparison, here (first, second) => first[0] - second[0]. It sorts the list in place and returns nothing. The subtraction trick is safe only because the values are small. With larger ones it can wrap: with variables 2000000000 and -2000000000, an unchecked int subtraction gives -294967296, which compares the wrong way. first[0].CompareTo(second[0]) has no such risk.
    • Tuple swap. (rootA, rootB) = (rootB, rootA); swaps two variables without a temporary. After int a = 1, b = 2; the same statement leaves a as 2 and b as 1.
    • Arrays are references. Find receives the caller's parent array itself, so the path halving it performs is visible to the caller. The parameter x is an int and is copied, so changing it inside Find leaves the caller's variable alone.
    • Iteration, not recursion. Find is a loop, so a long chain of parents can't overflow the call stack.
    • Arrays of arrays. The input is a jagged int[][], read as points[i][0] and points[i][1]. Each edge is also a small int[], which costs an object per edge: with 1000 points there are 499,500 of them.
    • Reused names in loops. Both for loops declare their own int i, which is allowed because each is scoped to its loop.

    Complexity

    Time: O(n² log n). Building the edges is O(n²). Sorting about n²/2 edges takes O(n² log n). With union by size and path halving, each Find costs almost constant time, so scanning the edges adds only about O(n²). A run on 1000 random points finishes well within a second.

    Space: O(n²). The edge list holds one three-element array per pair. The parent and size arrays add O(n).

    Edge cases and common mistakes

    • A single point. {{5,5}} returns 0. No edges exist, so the loop is skipped and total is returned as is.
    • Two points. {{0,0},{1000000,-1000000}} returns 2000000: one edge, with the full Manhattan distance.
    • Negative coordinates. The absolute values handle them. In the second example, the edge between (-2,5) and (-4,1) costs 2 + 4 = 6.
    • Collinear points. {{0,0},{0,1},{0,2},{0,3}} returns 3, three edges of cost 1.
    • Using Euclidean distance. The cost is the Manhattan distance, with no square roots.
    • Taking every edge. Without the root comparison, the algorithm would add the cost of all the edges, including those that close cycles.
    • Listing edges twice. Starting j at 0 instead of i + 1 includes each pair twice and pairs each point with itself, which doubles the sort work.
    • Merging roots incorrectly. Setting the parent of a point instead of its root leaves the rest of its group behind. The merge changes parent[rootB], not parent[edge[2]].
    • Sorting the other way. Taking the dearest edges first gives a spanning tree, but not the cheapest one.

    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},{1000000,-1000000}} gives 2000000.
    • {{-1000000,-1000000},{1000000,1000000}} gives 4000000.
    • {{0,0},{0,1},{0,2},{0,3}} gives 3.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free