The Question
Coding

Minimum Cost to Connect Cities

Given n cities and a list of weighted edges between them, find the minimum cost to connect all cities such that there is a path between every pair of cities, or return -1 if it is impossible.
Java
Kruskal's Algorithm
MST
Union-Find
Questions & Insights

Thinking Process

Recognize this as a classic Minimum Spanning Tree (MST) problem where we need to connect all nodes in a graph with the minimum total weight.
Use Kruskal's Algorithm because the input is provided as an edge list, making it natural to sort by weight and process edges greedily.
Employ a Disjoint Set Union (DSU) data structure with path compression and union-by-rank to efficiently track connected components and avoid cycles.
Verify connectivity: If the total number of edges successfully added to the MST is exactly n - 1, all cities are connected; otherwise, the graph is disconnected, and we return -1.
Implementation Breakdown

Problem Set

Functional Requirements: Find the minimum cost to connect n cities. Return -1 if impossible.
Constraints:
1 \le n \le 10^4
1 \le connections.length \le 10^4
1 \le x_i, y_i \le n
0 \le cost_i \le 10^5

Approach

Algorithm: Kruskal's Algorithm.
Data Structure: Disjoint Set Union (DSU) / Union-Find.
Complexity:
Time: O(E \log E) for sorting edges, where E is the number of connections. DSU operations are nearly O(1) due to path compression and union-by-rank (Inverse Ackermann function).
Space: O(n) to store the parent and rank arrays in the DSU.

Implementation