Connecting Cities With Minimum Cost (LeetCode 1135)
You will see how sorting the links and joining groups with Union-Find finds the cheapest way to connect every city.
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]]6n = 4, connections = [[1,2,3],[3,4,4]]-1⚖️Formal Constraints & Bounds
1 <= n <= 1041 <= connections.length <= 104connections[i].length == 31 <= xi, yi <= nxi != yi0 <= cost_i <= 105
Why It Works & Core Invariant
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`. |
Target: Connecting Cities With Minimum Cost (LeetCode 1135). Cities are labeled 1..n, so the list has n + 1 slots and index 0 is unused.
Maintains visited set or 3-color states (WHITE=unvisited, GREY=visiting/cycle, BLACK=processed) across adjacency lists.
Loop outer vertices 0..V-1 to handle disconnected subgraphs; explore edges via BFS/DFS/PriorityQueue.
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.
🪄 The Mathematical Harmony / Magic Trick
connections.sort(key=lambda e: e[2])for u, v, w in connections: root_u, root_v = find(u), find(v) if root_u != root_v: # different groups: safe to take parent[root_u] = root_v mst_cost += w edges_count += 1return mst_cost if edges_count == n - 1 else -1 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.
💡 Summary
Sort the edges, take each one that joins two different Union-Find groups, and stop at n - 1 edges. Fewer than n - 1 edges after the whole list means the cities can't all be joined: return -1. Sorting dominates: time, extra space for parent.
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
You will see how a senior engineer recognizes a minimum spanning tree and defends Kruskal's greedy choice.
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
return mst_cost if edges_count == n - 1 else -1: fewer thann - 1edges means the graph is disconnected, so return-1instead of the partial cost.parent[root_u] = root_v: join the roots, not the original nodes, or a group can end up with two roots.parent[x] = parent[parent[x]]: without path compression,findwalks long chains and the run slows to O(E * V).parent = list(range(n + 1)): cities are labeled 1..n.
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.
So: sort by cost, find(u) != find(v) then union and add, stop at n - 1 edges, else -1.
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)
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).
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
Triggers: "every city can reach every other city", "pay as little as possible in total", "list of [x, y, cost] links". Connect all nodes at minimum total edge weight: a minimum spanning tree, built with Kruskal's MST over the edge list.
cities, links, costs up to : the total is at most , which fits a 32-bit signed integer. Budget: time, space.
A disconnected input must return -1, not the partial cost. 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
The edges taken so far always form a forest that is part of some minimum spanning tree: each new edge is the cheapest remaining one between two separate groups.
`find` gives one root to exactly the cities the taken edges connect. `find(u) == find(v)` means the edge would close a cycle, so it is skipped; otherwise `parent[root_u] = root_v` merges the groups.
A spanning tree on n cities has exactly n - 1 edges. Reaching `edges_count == n - 1` returns `mst_cost`; finishing with fewer returns -1. Sorting gives O(E log E) time, `parent` O(V) space.
Connecting Cities With Minimum Cost (LeetCode 1135)
You will see how sorting the links and joining groups with Union-Find finds the cheapest way to connect every city.
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]]6n = 4, connections = [[1,2,3],[3,4,4]]-1⚖️Formal Constraints & Bounds
1 <= n <= 1041 <= connections.length <= 104connections[i].length == 31 <= xi, yi <= nxi != yi0 <= cost_i <= 105
Why It Works & Core Invariant
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`. |
Target: Connecting Cities With Minimum Cost (LeetCode 1135). Cities are labeled 1..n, so the list has n + 1 slots and index 0 is unused.
Maintains visited set or 3-color states (WHITE=unvisited, GREY=visiting/cycle, BLACK=processed) across adjacency lists.
Loop outer vertices 0..V-1 to handle disconnected subgraphs; explore edges via BFS/DFS/PriorityQueue.
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.
🪄 The Mathematical Harmony / Magic Trick
connections.sort(key=lambda e: e[2])for u, v, w in connections: root_u, root_v = find(u), find(v) if root_u != root_v: # different groups: safe to take parent[root_u] = root_v mst_cost += w edges_count += 1return mst_cost if edges_count == n - 1 else -1 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.
💡 Summary
Sort the edges, take each one that joins two different Union-Find groups, and stop at n - 1 edges. Fewer than n - 1 edges after the whole list means the cities can't all be joined: return -1. Sorting dominates: time, extra space for parent.
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
You will see how a senior engineer recognizes a minimum spanning tree and defends Kruskal's greedy choice.
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
return mst_cost if edges_count == n - 1 else -1: fewer thann - 1edges means the graph is disconnected, so return-1instead of the partial cost.parent[root_u] = root_v: join the roots, not the original nodes, or a group can end up with two roots.parent[x] = parent[parent[x]]: without path compression,findwalks long chains and the run slows to O(E * V).parent = list(range(n + 1)): cities are labeled 1..n.
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.
So: sort by cost, find(u) != find(v) then union and add, stop at n - 1 edges, else -1.
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)
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).
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
Triggers: "every city can reach every other city", "pay as little as possible in total", "list of [x, y, cost] links". Connect all nodes at minimum total edge weight: a minimum spanning tree, built with Kruskal's MST over the edge list.
cities, links, costs up to : the total is at most , which fits a 32-bit signed integer. Budget: time, space.
A disconnected input must return -1, not the partial cost. 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
The edges taken so far always form a forest that is part of some minimum spanning tree: each new edge is the cheapest remaining one between two separate groups.
`find` gives one root to exactly the cities the taken edges connect. `find(u) == find(v)` means the edge would close a cycle, so it is skipped; otherwise `parent[root_u] = root_v` merges the groups.
A spanning tree on n cities has exactly n - 1 edges. Reaching `edges_count == n - 1` returns `mst_cost`; finishing with fewer returns -1. Sorting gives O(E log E) time, `parent` O(V) space.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| Every node starts as its own group | parent = list(range(n + 1)) | Cities are labeled 1..n, so the list has n + 1 slots and index 0 is unused. |
| find returns a group's root, shortening the path as it goes | while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x] | Path halving keeps the trees shallow, so each find is almost O(1). |
| Cheapest edges first | connections.sort(key=lambda e: e[2]) | Kruskal's greedy choice: the cheapest edge between two groups is always safe. |
| Take an edge only if it joins two different groups | if root_u != root_v:
parent[root_u] = root_v | Equal roots mean the edge would close a cycle; different roots are joined at their roots. |
| Count the edges taken and stop at n - 1 | edges_count += 1
if edges_count == n - 1:
break | A spanning tree on n nodes has exactly n - 1 edges; nothing later can help. |
| Connected only if n - 1 edges were taken | return mst_cost if edges_count == n - 1 else -1 | Fewer edges after the whole list means at least two groups never met. |