Problem Description

You are given n cities numbered from 1 to n. Some pairs of cities are connected by bidirectional roads, and each road has a cost associated with building it. The input is a list of possible connections, where each connection is represented as [city1, city2, cost]. Your task is to connect all the cities together with the minimum possible total cost. If it is impossible to connect all the cities, return -1.

Key Constraints:

• Each city can be connected directly or indirectly to every other city.
• There is only one valid solution (the minimum cost is unique).
• You cannot reuse a connection in multiple places; each can only be used once.
• If it is not possible to connect all cities, you must return -1.

Thought Process

The core of this problem is to connect all cities with the smallest total cost, ensuring that every city is reachable from any other city. This is a classic "Minimum Spanning Tree" (MST) problem from graph theory.

Initial Intuition: You might think of trying all possible combinations of connections to see which set connects all cities at the lowest cost. However, this brute-force approach is impractical for larger inputs because the number of combinations grows exponentially.

Optimized Thinking: Instead, we realize that the MST algorithms (like Kruskal's or Prim's) are designed to solve exactly this type of problem efficiently. We need to:

• Pick the lowest-cost connections that don't create cycles.
• Ensure all cities are connected at the end.

Solution Approach

We can use Kruskal's Algorithm for this problem, which is well-suited when the graph is defined by an edge list. The steps are:

1. Sort all connections by their cost in ascending order.
2. Initialize a Union-Find (Disjoint Set Union) structure to keep track of connected components (groups of cities already connected).
3. Iterate through the sorted connections:
   • For each connection, check if the two cities are already connected (using Union-Find).
   • If not, connect them (union operation) and add the cost to the total.
   • If they are already connected, skip to avoid cycles.
4. After processing, check if all cities are connected:
   • If yes, return the total cost.
   • If not, return -1 (not all cities can be connected).

Why Union-Find? The Union-Find data structure allows us to efficiently check whether two cities are already connected (in the same set) and to merge sets when we connect two cities.

Example Walkthrough

Example Input:
n = 3
connections = [[1,2,5],[1,3,6],[2,3,1]]

Step-by-step:

1. Sort connections by cost: [[2,3,1],[1,2,5],[1,3,6]]
2. Initialize Union-Find for cities 1, 2, 3.
3. Take [2,3,1]: Cities 2 and 3 are not connected. Connect them, total cost = 1.
4. Take [1,2,5]: City 1 is not connected to 2/3. Connect 1 and 2, total cost = 1 + 5 = 6.
5. Take [1,3,6]: Cities 1 and 3 are already connected (through 2), skip.
6. All cities are now connected (one single set). Return total cost = 6.

Time and Space Complexity

Brute-force Approach:
- Time: Exponential, as it tries all possible combinations of connections.
- Space: Exponential, due to recursion stack or storing all combinations.

Optimized (Kruskal's Algorithm):

• Time Complexity: O(E log E + E * α(N)), where E is the number of connections, N is the number of cities, and α is the inverse Ackermann function (very slow-growing, nearly constant). Sorting dominates, so it's usually O(E log E).
• Space Complexity: O(N) for the Union-Find structure.

Code Implementation

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size + 1)]
        self.rank = [0] * (size + 1)
        self.count = size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        else:
            self.parent[rootY] = rootX
            if self.rank[rootX] == self.rank[rootY]:
                self.rank[rootX] += 1
        self.count -= 1
        return True

class Solution:
    def minimumCost(self, n, connections):
        uf = UnionFind(n)
        connections.sort(key=lambda x: x[2])
        total = 0
        for u, v, cost in connections:
            if uf.union(u, v):
                total += cost
        return total if uf.count == 1 else -1
    

class UnionFind {
public:
    vector<int> parent, rank;
    int count;
    UnionFind(int n) : parent(n + 1), rank(n + 1, 0), count(n) {
        for (int i = 0; i <= n; ++i) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else {
            parent[ry] = rx;
            if (rank[rx] == rank[ry]) rank[rx]++;
        }
        count--;
        return true;
    }
};

class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        UnionFind uf(n);
        sort(connections.begin(), connections.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[2] < b[2];
        });
        int total = 0;
        for (auto& conn : connections) {
            if (uf.unite(conn[0], conn[1])) {
                total += conn[2];
            }
        }
        return uf.count == 1 ? total : -1;
    }
};
    

class UnionFind {
    int[] parent, rank;
    int count;
    public UnionFind(int n) {
        parent = new int[n + 1];
        rank = new int[n + 1];
        count = n;
        for (int i = 0; i <= n; ++i) parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else {
            parent[ry] = rx;
            if (rank[rx] == rank[ry]) rank[rx]++;
        }
        count--;
        return true;
    }
}

class Solution {
    public int minimumCost(int n, int[][] connections) {
        UnionFind uf = new UnionFind(n);
        Arrays.sort(connections, (a, b) -> a[2] - b[2]);
        int total = 0;
        for (int[] conn : connections) {
            if (uf.union(conn[0], conn[1])) {
                total += conn[2];
            }
        }
        return uf.count == 1 ? total : -1;
    }
}
    

class UnionFind {
    constructor(n) {
        this.parent = Array(n + 1).fill(0).map((_, i) => i);
        this.rank = Array(n + 1).fill(0);
        this.count = n;
    }
    find(x) {
        if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }
    union(x, y) {
        let rx = this.find(x), ry = this.find(y);
        if (rx === ry) return false;
        if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
        else {
            this.parent[ry] = rx;
            if (this.rank[rx] === this.rank[ry]) this.rank[rx]++;
        }
        this.count--;
        return true;
    }
}

var minimumCost = function(n, connections) {
    let uf = new UnionFind(n);
    connections.sort((a, b) => a[2] - b[2]);
    let total = 0;
    for (let [u, v, cost] of connections) {
        if (uf.union(u, v)) total += cost;
    }
    return uf.count === 1 ? total : -1;
};
    

Summary

In summary, the "Connecting Cities With Minimum Cost" problem is a textbook application of the Minimum Spanning Tree concept. By leveraging Kruskal's algorithm and an efficient Union-Find structure, we can connect all cities with the lowest possible cost, or quickly determine if it's impossible. The key insight is to always connect the cheapest available pair of cities that doesn't form a cycle, and to use Union-Find to track connectivity efficiently. This approach is both elegant and optimal for the problem constraints.