Connecting Cities With Minimum Cost

Medium Graphs Minimum Spanning Tree Original on LeetCode

Reported atGoogle

Connecting Cities With Minimum Cost is a medium graphs problem solved with the minimum spanning tree pattern. The best approach, optimal (kruskal with union-find), runs in O(E log E) time and O(V + E) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (kruskal with a dfs connectivity check) up.

Problem

There are n cities numbered from 1 to n. You are given a list connections, where connections[i] = [x, y, cost] says that a two-way road between city x and city y can be built for cost. There may be more than one possible road between the same pair of cities.

Choose roads to build so that every city can reach every other city (directly or through other cities), while paying the smallest possible total cost. Return that minimum total cost, or -1 if it is impossible to connect all the cities.

Examples

Example 1

Input
n = 4, connections = [[1,2,4],[2,3,1],[3,4,6],[1,3,3],[2,4,5]]
Output
9
Why
Build 2-3 (cost 1), 1-3 (cost 3) and 2-4 (cost 5). Every city is reachable and no cheaper set of roads does that.

Example 2

Input
n = 3, connections = [[1,2,7]]
Output
-1
Why
No road touches city 3, so it can never be connected.

Example 3

Input
n = 3, connections = [[1,2,5],[1,2,2],[2,3,4]]
Output
6
Why
There are two possible roads between 1 and 2; take the cheaper one (2) plus 2-3 (4).

Constraints

  • 1 <= n <= 10^4
  • 1 <= connections.length <= 10^4
  • connections[i].length == 3
  • 1 <= x_i, y_i <= n, x_i != y_i
  • 0 <= cost_i <= 10^5

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (Kruskal with a DFS connectivity check)O(E log E + E · (V + E))O(V + E)
Optimal (Kruskal with Union-Find)O(E log E)O(V + E)

1Brute force (Kruskal with a DFS connectivity check)

TimeO(E log E + E · (V + E))Sorting costs E log E; each of the E roads may trigger a DFS over the chosen forest.
SpaceO(V + E)The chosen roads as adjacency lists plus the DFS stack and visited array.

Sort the roads by cost. Keep a graph of the roads chosen so far. For each road in order, run a DFS from one city to see whether the other is already reachable; if not, add the road. When n - 1 roads are chosen, every city is connected.

  1. Sort connections by cost.
  2. For each road (x, y, c): DFS over the chosen roads from x. If y is not reached, add the road to the chosen graph, add c to the total and count it.
  3. Return the total if n - 1 roads were chosen, otherwise -1.
class Solution {
    public int minimumCost(int n, int[][] connections) {
        int[][] edges = connections.clone();
        Arrays.sort(edges, (a, b) -> a[2] - b[2]);
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        int total = 0, used = 0;
        for (int[] e : edges) {
            if (used == n - 1) break;
            if (reachable(adj, n, e[0], e[1])) continue;
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
            total += e[2];
            used++;
        }
        return used == n - 1 ? total : -1;
    }

    private boolean reachable(List<List<Integer>> adj, int n, int from, int to) {
        boolean[] seen = new boolean[n + 1];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(from);
        seen[from] = true;
        while (!stack.isEmpty()) {
            int u = stack.pop();
            if (u == to) return true;
            for (int v : adj.get(u)) {
                if (!seen[v]) {
                    seen[v] = true;
                    stack.push(v);
                }
            }
        }
        return false;
    }
}

2Optimal (Kruskal with Union-Find)

TimeO(E log E)Sorting dominates; each union-find operation is nearly O(1) (inverse Ackermann).
SpaceO(V + E)Parent and size arrays of size V, plus the sorted copy of the roads.

Same greedy order as before, but replace the DFS with a disjoint set union. find tells which component a city is in; a road is taken only when its two cities are in different components, and then the components are merged. With path compression and union by size each check is almost constant time.

  1. Sort connections by cost; parent[i] = i and size[i] = 1 for every city.
  2. For each road (x, y, c): if find(x) != find(y), union them, add c to the total and count the road.
  3. Stop early once n - 1 roads are taken.
  4. Return the total if n - 1 roads were taken, otherwise -1.
class Solution {
    private int[] parent, size;

    public int minimumCost(int n, int[][] connections) {
        int[][] edges = connections.clone();
        Arrays.sort(edges, (a, b) -> a[2] - b[2]);
        parent = new int[n + 1];
        size = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        int total = 0, used = 0;
        for (int[] e : edges) {
            if (used == n - 1) break;
            int a = find(e[0]), b = find(e[1]);
            if (a == b) continue;
            if (size[a] < size[b]) { int t = a; a = b; b = t; }
            parent[b] = a;
            size[a] += size[b];
            total += e[2];
            used++;
        }
        return used == n - 1 ? total : -1;
    }

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}

Edge cases to test

  • Only two cities and a single road between them
  • Several roads between the same pair of cities: only the cheapest can matter
  • The graph is split into separate parts: return -1
  • Roads with cost 0

Hints

Hint 1

You need a set of roads that touches every city, has no cycle and costs as little as possible. That is a minimum spanning tree.

Hint 2

Look at roads from cheapest to most expensive. A road is useful only if its two cities are not yet connected by the roads you already picked.

Hint 3

Answering "are these two cities already connected?" quickly is exactly what a Union-Find (disjoint set) structure does.

FAQ

What is the best time complexity for Connecting Cities With Minimum Cost?

Optimal (Kruskal with Union-Find) runs in O(E log E) time and O(V + E) extra space. Sorting dominates; each union-find operation is nearly O(1) (inverse Ackermann).

Which pattern does Connecting Cities With Minimum Cost use?

It is a graphs problem that uses the minimum spanning tree pattern.

Is there a brute force solution for Connecting Cities With Minimum Cost?

Yes. Brute force (Kruskal with a DFS connectivity check) takes O(E log E + E · (V + E)) time and O(V + E) space. Sort the roads by cost.

Which edge cases should I test for Connecting Cities With Minimum Cost?

Only two cities and a single road between them; Several roads between the same pair of cities: only the cheapest can matter; The graph is split into separate parts: return -1; Roads with cost 0.