Connecting Cities With Minimum Cost (LeetCode 1135)
There are n cities, labeled 1 to n. Each connections[i] = [xi, yi, cost_i] says you can build a two-way link between city xi and city yi for cost_i.
Choose links so that every city can reach every other city through built links, and pay as little as possible in total. Return that smallest total, or -1 if even building every link leaves some cities cut off.
Worked Examples
n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]62-3 for 1 and 1-2 for 5.n = 4, connections = [[1,2,3],[3,4,4]]-1{1, 2} to the pair {3, 4}, so the cities can't all be connected.⚖️Formal Constraints & Bounds
1 <= n <= 1041 <= connections.length <= 104connections[i].length == 31 <= xi, yi <= nxi != yi0 <= cost_i <= 105
Core Insight
Take links from cheapest to most expensive and keep each one that joins two cities not yet connected (a Union-Find find tells); n - 1 kept links is a cheapest spanning tree, fewer means some city can't be reached.
Real-World Scenario & Production Applications
Laying cable, fibre or pipes between sites at the smallest total cost is a minimum spanning tree problem; so is clustering by stopping Kruskal early (single-linkage clustering). The same sort-and-union loop runs over any weighted edge list.
Step-by-Step Execution Trace Table
Input n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]], sorted by cost: [2,3,1], [1,2,5], [1,3,6].
| Step | Edge [u, v, w] | find(u), find(v) | Same group? | Action | mst_cost | edges_count |
|---|---|---|---|---|---|---|
| 1 | [2, 3, 1] | 2, 3 | No | take it, parent[2] = 3 | 1 | 1 |
| 2 | [1, 2, 5] | 1, 3 | No | take it, parent[1] = 3 | 6 | 2 = n - 1, stop |
| End | edges_count == n - 1, return mst_cost | 6 |
Input n = 4, connections = [[1,2,3],[3,4,4]]: both edges are taken (edges_count = 2), the list ends with 2 < n - 1 = 3, so the answer is -1.
n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]6Input n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]], sorted by cost: [2,3,1], [1,2,5], [1,3,6].
| Step | Edge [u, v, w] | find(u), find(v) | Same group? | Action | mst_cost | edges_count |
|---|---|---|---|---|---|---|
| 1 | [2, 3, 1] | 2, 3 | No | take it, parent[2] = 3 | 1 | 1 |
| 2 | [1, 2, 5] | 1, 3 | No | take it, parent[1] = 3 | 6 | 2 = n - 1, stop |
| End | edges_count == n - 1, return mst_cost | 6 |
Input n = 4, connections = [[1,2,3],[3,4,4]]: both edges are taken (edges_count = 2), the list ends with 2 < n - 1 = 3, so the answer is -1.
| 1 | The cheapest link between two separate groups is always safe to build; a link inside one group only closes a cycle. |
| 2 | `find(u) != find(v)` says the ends are in different groups: take the edge, join the roots (`parent[root_u] = root_v`), add `w` to `mst_cost`, and count it in `edges_count`. |
| 3 | `parent = list(range(n + 1))`, a `find` with path halving, sort `connections` by cost, loop and take safe edges, stop at `n - 1` edges. |
| 4 | The trap: return `mst_cost` only if `edges_count == n - 1`; fewer edges means the cities are not all connected, so return `-1`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
To join every city at the lowest total cost you need a minimum spanning tree: n - 1 links, no cycles, smallest total weight. Kruskal's algorithm builds it greedily: look at the links from cheapest to most expensive, and take a link only when its two cities are still in different groups. A Union-Find (parent plus find) answers "same group?" almost instantly, and joining two groups is one assignment.
🏟️ The Analogy: Building Bridges Between Islands
Picture every city as its own island. You have a price list of possible bridges. Go down the list from the cheapest: if a bridge links two islands that are not yet reachable from each other, build it and treat the two as one bigger island. If they are already reachable, the bridge would only make a loop, so skip it. When everything is one island you are done; if the list runs out first, some islands can never be reached.
🔑 Why It Works
Why the cheapest crossing edge is safe: any full wiring must cross the gap between two separate groups somewhere; if it used a more expensive crossing, swapping in the cheaper one keeps everything connected and never costs more. An edge whose ends share a root would only close a cycle, so skipping it loses nothing.
Returning the partial cost when the graph is disconnected: after the loop,
edges_count < n - 1means some cities were never reached. Return-1, notmst_cost: onn = 4,[[1,2,3],[3,4,4]]the partial cost is 7 but the answer is-1.Joining the nodes instead of the roots:
parent[u] = vcan cutuoff from its own group and leave two roots for one group. Always joinparent[root_u] = root_v.No path compression: without the
parent[x] = parent[parent[x]]step, chains grow and eachfindcan walkO(n)links, making the whole run O(E * V).Off-by-one on labels: cities are labeled
1..n, soparentneedsn + 1slots;list(range(n))crashes on cityn.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Connect all the cities" with the "minimum total cost" over a list of weighted links: every city must be reachable, but the cost is paid per link, not per route. That is a minimum spanning tree, and with the links given as an edge list, Kruskal's MST (sort plus Union-Find) is the direct fit.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The edges taken so far form a forest that is part of some minimum spanning tree, and find gives one root to exactly the cities they connect; an edge is taken exactly when find(u) != find(v).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
connections.sort(key=lambda e: e[2]): sort by the cost, the third value. A plainconnections.sort()orders by the first city, so expensive links can be taken first: Example 1 returns 11 instead of 6.Two links between the same pair of cities need no special case: once the cheaper one is taken, the other has
find(u) == find(v)and is skipped like any link that would close a cycle.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is a minimum spanning tree, so I'd use Kruskal's MST. I sort the connections by cost and keep a Union-Find over the cities. For each connection, cheapest first, I find both cities' roots. If the roots differ, the link joins two separate groups, so I take it: I join the roots, add its cost, and count it. If the roots match, it would only close a cycle, so I skip it. Taking the cheapest link across any gap is safe, because any full wiring must cross that gap somewhere and swapping in the cheaper link never costs more. I stop once I have n minus one links. The trap is the end: if I finish the list with fewer than n minus one links, some cities are unreachable and I return minus one, not the partial cost. Sorting dominates, so it's O(E log E) time, with O(V) space for the parent array.
Complexity & Mathematical Proof
O(E log E)
Look at the code: connections.sort(key=lambda e: e[2]) costs O(E log E). The loop visits each of the E edges at most once; each iteration calls find twice, and with path halving a find costs amortized O(log V) at worst (nearly constant in practice), which is below the sort's per-edge O(log E). Total: O(E log E).
O(V)
parent holds n + 1 entries: O(V). The edges are sorted in place in the input list; the counters are O(1). (Python's sort may use a temporary buffer while it runs.)
T(V, E) = O(E log E) + E · O(find) = O(E log E)
Derivation Progression
O(V)
parent = list(range(n + 1)).
O(E log E)
connections.sort(key=lambda e: e[2]).
E × 2 finds
Each edge is looked at once; find with path halving is nearly constant, at most O(log V) amortized.
O(E log E)
The sort dominates the scan.
Variable Definitions
Number of cities, n
Number of candidate links, len(connections)
Memory Architecture & Bounds
O(1): find is iterative
O(V): the parent array
O(1): one integer
Boundary Best / Worst Cases
: the sort runs even if the first n - 1 edges already connect everything
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Scale signal: trying every set of links is exponential; sorting the links once and one near-constant find pair per link is about steps.
cities, links, costs up to : the total is at most , which fits a 32-bit signed integer.
At scale, Kruskal needs the whole edge list sorted up front; when edges arrive as a stream or don't fit in memory, sort externally or use Prim's algorithm on an adjacency structure instead.
Core Algorithmic State Invariants
- Example 1, Cheapest First
Sorted by cost: 2-3 (1), 1-2 (5), 1-3 (6). Link 2-3 joins two groups, then 1-2 joins city 1: that is n - 1 = 2 links, so the loop stops at 6 and never reads 1-3.
- A Link Inside One Group Is Skipped
n = 4, [[1,2,1],[2,3,2],[1,3,3],[3,4,4]]: after 1-2 and 2-3, find(1) == find(3), so 1-3 would close a cycle and is skipped; 3-4 completes the tree at 1 + 2 + 4 = 7.
- Ties Change the Tree, Not the Cost
When two links cost the same, the sort may put either first, and the chosen links can differ, but every minimum spanning tree has the same total cost, so the answer does not change.
Connecting Cities With Minimum Cost (LeetCode 1135)
There are n cities, labeled 1 to n. Each connections[i] = [xi, yi, cost_i] says you can build a two-way link between city xi and city yi for cost_i.
Choose links so that every city can reach every other city through built links, and pay as little as possible in total. Return that smallest total, or -1 if even building every link leaves some cities cut off.
Worked Examples
n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]62-3 for 1 and 1-2 for 5.n = 4, connections = [[1,2,3],[3,4,4]]-1{1, 2} to the pair {3, 4}, so the cities can't all be connected.⚖️Formal Constraints & Bounds
1 <= n <= 1041 <= connections.length <= 104connections[i].length == 31 <= xi, yi <= nxi != yi0 <= cost_i <= 105
Core Insight
Take links from cheapest to most expensive and keep each one that joins two cities not yet connected (a Union-Find find tells); n - 1 kept links is a cheapest spanning tree, fewer means some city can't be reached.
Real-World Scenario & Production Applications
Laying cable, fibre or pipes between sites at the smallest total cost is a minimum spanning tree problem; so is clustering by stopping Kruskal early (single-linkage clustering). The same sort-and-union loop runs over any weighted edge list.
Step-by-Step Execution Trace Table
Input n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]], sorted by cost: [2,3,1], [1,2,5], [1,3,6].
| Step | Edge [u, v, w] | find(u), find(v) | Same group? | Action | mst_cost | edges_count |
|---|---|---|---|---|---|---|
| 1 | [2, 3, 1] | 2, 3 | No | take it, parent[2] = 3 | 1 | 1 |
| 2 | [1, 2, 5] | 1, 3 | No | take it, parent[1] = 3 | 6 | 2 = n - 1, stop |
| End | edges_count == n - 1, return mst_cost | 6 |
Input n = 4, connections = [[1,2,3],[3,4,4]]: both edges are taken (edges_count = 2), the list ends with 2 < n - 1 = 3, so the answer is -1.
n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]6Input n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]], sorted by cost: [2,3,1], [1,2,5], [1,3,6].
| Step | Edge [u, v, w] | find(u), find(v) | Same group? | Action | mst_cost | edges_count |
|---|---|---|---|---|---|---|
| 1 | [2, 3, 1] | 2, 3 | No | take it, parent[2] = 3 | 1 | 1 |
| 2 | [1, 2, 5] | 1, 3 | No | take it, parent[1] = 3 | 6 | 2 = n - 1, stop |
| End | edges_count == n - 1, return mst_cost | 6 |
Input n = 4, connections = [[1,2,3],[3,4,4]]: both edges are taken (edges_count = 2), the list ends with 2 < n - 1 = 3, so the answer is -1.
| 1 | The cheapest link between two separate groups is always safe to build; a link inside one group only closes a cycle. |
| 2 | `find(u) != find(v)` says the ends are in different groups: take the edge, join the roots (`parent[root_u] = root_v`), add `w` to `mst_cost`, and count it in `edges_count`. |
| 3 | `parent = list(range(n + 1))`, a `find` with path halving, sort `connections` by cost, loop and take safe edges, stop at `n - 1` edges. |
| 4 | The trap: return `mst_cost` only if `edges_count == n - 1`; fewer edges means the cities are not all connected, so return `-1`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
To join every city at the lowest total cost you need a minimum spanning tree: n - 1 links, no cycles, smallest total weight. Kruskal's algorithm builds it greedily: look at the links from cheapest to most expensive, and take a link only when its two cities are still in different groups. A Union-Find (parent plus find) answers "same group?" almost instantly, and joining two groups is one assignment.
🏟️ The Analogy: Building Bridges Between Islands
Picture every city as its own island. You have a price list of possible bridges. Go down the list from the cheapest: if a bridge links two islands that are not yet reachable from each other, build it and treat the two as one bigger island. If they are already reachable, the bridge would only make a loop, so skip it. When everything is one island you are done; if the list runs out first, some islands can never be reached.
🔑 Why It Works
Why the cheapest crossing edge is safe: any full wiring must cross the gap between two separate groups somewhere; if it used a more expensive crossing, swapping in the cheaper one keeps everything connected and never costs more. An edge whose ends share a root would only close a cycle, so skipping it loses nothing.
Returning the partial cost when the graph is disconnected: after the loop,
edges_count < n - 1means some cities were never reached. Return-1, notmst_cost: onn = 4,[[1,2,3],[3,4,4]]the partial cost is 7 but the answer is-1.Joining the nodes instead of the roots:
parent[u] = vcan cutuoff from its own group and leave two roots for one group. Always joinparent[root_u] = root_v.No path compression: without the
parent[x] = parent[parent[x]]step, chains grow and eachfindcan walkO(n)links, making the whole run O(E * V).Off-by-one on labels: cities are labeled
1..n, soparentneedsn + 1slots;list(range(n))crashes on cityn.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Connect all the cities" with the "minimum total cost" over a list of weighted links: every city must be reachable, but the cost is paid per link, not per route. That is a minimum spanning tree, and with the links given as an edge list, Kruskal's MST (sort plus Union-Find) is the direct fit.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The edges taken so far form a forest that is part of some minimum spanning tree, and find gives one root to exactly the cities they connect; an edge is taken exactly when find(u) != find(v).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
connections.sort(key=lambda e: e[2]): sort by the cost, the third value. A plainconnections.sort()orders by the first city, so expensive links can be taken first: Example 1 returns 11 instead of 6.Two links between the same pair of cities need no special case: once the cheaper one is taken, the other has
find(u) == find(v)and is skipped like any link that would close a cycle.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is a minimum spanning tree, so I'd use Kruskal's MST. I sort the connections by cost and keep a Union-Find over the cities. For each connection, cheapest first, I find both cities' roots. If the roots differ, the link joins two separate groups, so I take it: I join the roots, add its cost, and count it. If the roots match, it would only close a cycle, so I skip it. Taking the cheapest link across any gap is safe, because any full wiring must cross that gap somewhere and swapping in the cheaper link never costs more. I stop once I have n minus one links. The trap is the end: if I finish the list with fewer than n minus one links, some cities are unreachable and I return minus one, not the partial cost. Sorting dominates, so it's O(E log E) time, with O(V) space for the parent array.
Complexity & Mathematical Proof
O(E log E)
Look at the code: connections.sort(key=lambda e: e[2]) costs O(E log E). The loop visits each of the E edges at most once; each iteration calls find twice, and with path halving a find costs amortized O(log V) at worst (nearly constant in practice), which is below the sort's per-edge O(log E). Total: O(E log E).
O(V)
parent holds n + 1 entries: O(V). The edges are sorted in place in the input list; the counters are O(1). (Python's sort may use a temporary buffer while it runs.)
T(V, E) = O(E log E) + E · O(find) = O(E log E)
Derivation Progression
O(V)
parent = list(range(n + 1)).
O(E log E)
connections.sort(key=lambda e: e[2]).
E × 2 finds
Each edge is looked at once; find with path halving is nearly constant, at most O(log V) amortized.
O(E log E)
The sort dominates the scan.
Variable Definitions
Number of cities, n
Number of candidate links, len(connections)
Memory Architecture & Bounds
O(1): find is iterative
O(V): the parent array
O(1): one integer
Boundary Best / Worst Cases
: the sort runs even if the first n - 1 edges already connect everything
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Scale signal: trying every set of links is exponential; sorting the links once and one near-constant find pair per link is about steps.
cities, links, costs up to : the total is at most , which fits a 32-bit signed integer.
At scale, Kruskal needs the whole edge list sorted up front; when edges arrive as a stream or don't fit in memory, sort externally or use Prim's algorithm on an adjacency structure instead.
Core Algorithmic State Invariants
- Example 1, Cheapest First
Sorted by cost: 2-3 (1), 1-2 (5), 1-3 (6). Link 2-3 joins two groups, then 1-2 joins city 1: that is n - 1 = 2 links, so the loop stops at 6 and never reads 1-3.
- A Link Inside One Group Is Skipped
n = 4, [[1,2,1],[2,3,2],[1,3,3],[3,4,4]]: after 1-2 and 2-3, find(1) == find(3), so 1-3 would close a cycle and is skipped; 3-4 completes the tree at 1 + 2 + 4 = 7.
- Ties Change the Tree, Not the Cost
When two links cost the same, the sort may put either first, and the chosen links can differ, but every minimum spanning tree has the same total cost, so the answer does not change.