Minimum Spanning Tree

Question

There are n cities labeled from 1 to n. You are given the integer n and an array connections where connections[i] = [xi, yi, costi] indicates that the cost of connecting city xi and city yi (bidirectional connection) is costi.

Return the minimum cost to connect all the n cities such that there is at least one path between each pair of cities. If it is impossible to connect all the n cities, return -1,

The cost is the sum of the connections’ costs used.

Example 1:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.

Example 2:

Input: n = 4, connections = [[1,2,3],[3,4,4]]
Output: -1
Explanation: There is no way to connect all cities even if all edges are used.

Constraints:

  • 1 <= n <= 104
  • 1 <= connections.length <= 104
  • connections[i].length == 3
  • 1 <= xi, yi <= n
  • xi != yi
  • 0 <= costi <= 105

Solution

class Solution {
    int[] rank;
    int[] root;

    public int minimumCost(int n, int[][] connections) {
        rank = new int[n + 1];
        root = new int[n + 1];

        for (var i = 0; i < n; i++) {
            rank[i] = 1;
            root[i] = i;
        }

        Arrays.sort(connections, (l, r) -> {
            return Integer.compare(l[2], r[2]);
        });

        var cost = 0;
        for (var c : connections) {
            if (find(c[0]) != find(c[1])) {
                cost += c[2];
                union(c[0], c[1]);
            }
        }

        for (var i = 1; i < n; i++) {
            if (find(i) != find(i -1)) {
                return -1;
            }
        }

        return cost;
    }

    void union(int x, int y) {
        var rootX = root[x];
        var rootY = root[y];
        if (rank[rootX] > rank[rootY]) {
            rootX ^= rootY;
            rootY ^= rootX;
            rootX ^= rootY;
        }
        root[rootX] = rootY;
        rank[rootY] += rank[rootX];
    }

    int find(int x) {
        if (root[x] != x) {
            root[x] = find(root[x]);
        }
        return root[x];
    }
}

Recent posts from blogs that I like

Painting the whole truth, and nothing but the truth 1

She started as a now lost painting by Apelles, then later gained a mirror and a well, following old proverbs. She has ended up with a burning torch, and the support of Father Time.

via The Eclectic Light Company

Working with designers

I love working with designers, in part because (unlike managers and product managers) they’re culturally different from engineers. However, having more than one designer on a team is asking for trouble, and I have complicated negative thoughts about design systems.

Design is a strange role

Designers...

via Sean Goedecke

Want to Rent an Internet Address at the White House?

Several staffers at the White House are using computers or mobile devices equipped with residential proxy services that render their internet address available for others to rent, security experts warned today. One of the proxy services is a Russian company whose founder's web hosting business was g...

via Krebs on Security