Editorial
Core insight
Connecting Cities With Minimum Cost · Graph Traversal Patterns (DFS & BFS)
Core Insight for Connecting Cities With Minimum Cost
The transition from brute force to an optimal solution relies on the Greedy Choice Property. In the context of Connecting Cities With Minimum Cost, if we have a choice between multiple edges to connect two previously unconnected components, selecting the edge with the minimum cost is always locally optimal and leads to a globally optimal solution.
The key invariant enforced by the pattern is that we never add an edge that creates a cycle. A cycle implies redundancy; if a cycle exists, we can remove the most expensive edge in that cycle to reduce cost while maintaining connectivity.
Visual Description: Imagine the state of the system as a collection of disjoint sets. Initially, every city is an isolated island (a set of size 1). The algorithm processes connections in ascending order of cost.
- We inspect the cheapest connection
[u, v, cost]. - We check the
parentarray of our Disjoint Set Union (DSU) structure. - If
find(u)is distinct fromfind(v), the cities belong to different components. We performunion(u, v), effectively merging two trees into one larger tree. Visually, a link is drawn between the two islands. - If
find(u)is identical tofind(v), the cities are already connected via some other path. Adding this edge would close a loop (cycle). We discard it. - This process repeats until we have selected edges or exhausted the list.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 1135: Connecting Cities With Minimum Cost Solution & Explanation
Problem Overview
TL;DR: The optimal solution utilizes Kruskal’s Algorithm (a Minimum Spanning Tree approach) to greedily select the lowest-cost connections that merge disjoint sets of cities until all cities form a single connected component.
We are provided with N cities and a list of potential bidirectional connections, each with an associated cost. The objective of LeetCode 1135 is to determine the minimum total cost required to ensure that a path exists between every pair of cities. This is a classic application of finding a Minimum Spanning Tree (MST) in a weighted undirected graph. If the cities cannot be fully connected, the solution must return -1.
Brute Force Approach for Connecting Cities With Minimum Cost
The brute force strategy attempts to find the minimum cost by generating all possible subgraphs that connect all cities and calculating their costs.
- Generate every possible subset of the given
connections. - For each subset, check if it forms a valid spanning tree (i.e., it connects all
Ncities and has exactlyN-1edges). - If valid, calculate the sum of costs.
- Track the minimum sum encountered.
Pseudo-code for the naive logic:
min_cost = infinity
for every subset S of connections:
if S connects all N cities:
current_cost = sum of weights in S
min_cost = min(min_cost, current_cost)
return min_cost if changed else -1Time Complexity: The number of subsets is , where is the number of connections. Checking connectivity takes . This results in a complexity of , which is exponential. Given can be up to 10,000, this approach is computationally infeasible and will result in a Time Limit Exceeded (TLE).
Why it fails: The brute force method ignores the specific structural property of the problem: we always prefer cheaper edges over expensive ones. Enumerating combinations fails to leverage this greedy property.
Algorithm Strategy: Graph - Minimum Spanning Tree (Kruskal)
We will implement Kruskal's Algorithm using the Disjoint Set Union (DSU) data structure. This aligns with the subpattern effectively handling edge-list inputs.
- Sort Edges: First, sort the
connectionsarray based on the cost in ascending order. This allows us to attempt the cheapest connections first. - Initialize DSU: Create a DSU structure to manage
Ncities. Initially, each city is its own parent. - Iterate and Merge: Traverse the sorted connections. For each connection
(city1, city2, cost):- Find the root parent of
city1andcity2. - If the roots are different, these cities are currently in disjoint components. Union them and add the
costto our total. Increment an edge counter. - If the roots are the same, skip the edge to avoid cycles.
- Find the root parent of
- Verification: A valid MST for
Nnodes must have exactlyN - 1edges. If the edge counter equalsN - 1after the loop, return the total cost. Otherwise, return -1 (the graph is disconnected).
Execution Flow
- Input Parsing: We receive
Nandconnections. - Sorting: The
connectionslist is sorted by the third element (cost). - DSU Setup: Initialize an array
parentof sizeN + 1whereparent[i] = i. - Traversal:
- Pointer starts at the first (cheapest) edge.
- Check if the two cities of the edge share a common root using path compression.
- Case A (Disjoint): Perform union by rank/size. Add cost to
total_cost. Incrementedges_count. - Case B (Connected): Do nothing. Move to the next edge.
- Termination:
- Check if
edges_count == N - 1. - If true, return
total_cost. - If false, return
-1.
- Check if
Proof of Correctness
Kruskal's algorithm is correct due to the Cut Property. The Cut Property states that for any cut (a partition of the vertices into two disjoint sets) of the graph, if an edge has the minimum weight among all edges crossing the cut, then this edge belongs to some MST of the graph.
By sorting edges and iterating from smallest to largest, Kruskal's algorithm always selects the minimum weight edge that connects two disjoint components (effectively crossing a cut between those components). Therefore, every edge chosen is part of the optimal solution.
Pattern Reuse Notes
The Graph - Minimum Spanning Tree pattern used here is directly applicable to several other popular interview questions:
- LeetCode 1584: Min Cost to Connect All Points - Similar logic, but the edges are implicit (Manhattan distance between coordinates) rather than explicitly given.
- LeetCode 1168: Optimize Water Distribution in a Village - This problem introduces "virtual nodes" but fundamentally relies on the same MST principles (Prim's or Kruskal's) to minimize cost.
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 1135
1#include <vector>
2#include <algorithm>
3#include <numeric>
4
5using namespace std;
6
7class Solution {
8 struct DSU {
9 vector<int> parent;
10 vector<int> rank;
11
12 DSU(int n) {
13 parent.resize(n + 1);
14 iota(parent.begin(), parent.end(), 0);
15 rank.assign(n + 1, 0);
16 }
17
18 int find(int x) {
19 if (parent[x] != x) {
20 parent[x] = find(parent[x]); // Path compression
21 }
22 return parent[x];
23 }
24
25 bool unite(int x, int y) {
26 int rootX = find(x);
27 int rootY = find(y);
28
29 if (rootX != rootY) {
30 if (rank[rootX] > rank[rootY]) {
31 parent[rootY] = rootX;
32 } else if (rank[rootX] < rank[rootY]) {
33 parent[rootX] = rootY;
34 } else {
35 parent[rootY] = rootX;
36 rank[rootX]++;
37 }
38 return true;
39 }
40 return false;
41 }
42 };
43
44public:
45 int minimumCost(int N, vector<vector<int>>& connections) {
46 // Sort connections by cost (ascending)
47 sort(connections.begin(), connections.end(), [](const vector<int>& a, const vector<int>& b) {
48 return a[2] < b[2];
49 });
50
51 DSU dsu(N);
52 int totalCost = 0;
53 int edgesCount = 0;
54
55 for (const auto& conn : connections) {
56 int u = conn[0];
57 int v = conn[1];
58 int cost = conn[2];
59
60 // If uniting u and v is successful (they were disjoint), add cost
61 if (dsu.unite(u, v)) {
62 totalCost += cost;
63 edgesCount++;
64 }
65
66 // Optimization: If we have found N-1 edges, we are done
67 if (edgesCount == N - 1) {
68 return totalCost;
69 }
70 }
71
72 return -1;
73 }
74};Java Solution for LeetCode 1135
1import java.util.Arrays;
2
3class Solution {
4 // Inner class for Disjoint Set Union
5 class DSU {
6 int[] parent;
7 int[] rank;
8
9 public DSU(int n) {
10 parent = new int[n + 1];
11 rank = new int[n + 1];
12 for (int i = 0; i <= n; i++) {
13 parent[i] = i;
14 rank[i] = 1;
15 }
16 }
17
18 public int find(int x) {
19 if (parent[x] != x) {
20 parent[x] = find(parent[x]); // Path compression
21 }
22 return parent[x];
23 }
24
25 public boolean union(int x, int y) {
26 int rootX = find(x);
27 int rootY = find(y);
28
29 if (rootX != rootY) {
30 if (rank[rootX] > rank[rootY]) {
31 parent[rootY] = rootX;
32 } else if (rank[rootX] < rank[rootY]) {
33 parent[rootX] = rootY;
34 } else {
35 parent[rootY] = rootX;
36 rank[rootX]++;
37 }
38 return true;
39 }
40 return false;
41 }
42 }
43
44 public int minimumCost(int N, int[][] connections) {
45 // Sort connections by cost
46 Arrays.sort(connections, (a, b) -> Integer.compare(a[2], b[2]));
47
48 DSU dsu = new DSU(N);
49 int totalCost = 0;
50 int edgesCount = 0;
51
52 for (int[] conn : connections) {
53 int u = conn[0];
54 int v = conn[1];
55 int cost = conn[2];
56
57 if (dsu.union(u, v)) {
58 totalCost += cost;
59 edgesCount++;
60
61 // Early exit if MST is complete
62 if (edgesCount == N - 1) {
63 return totalCost;
64 }
65 }
66 }
67
68 return -1;
69 }
70}Python Solution for LeetCode 1135
1class Solution:
2 def minimumCost(self, N: int, connections: list[list[int]]) -> int:
3 # Sort connections by cost (3rd element)
4 connections.sort(key=lambda x: x[2])
5
6 parent = list(range(N + 1))
7
8 def find(i):
9 if parent[i] != i:
10 parent[i] = find(parent[i]) # Path compression
11 return parent[i]
12
13 def union(i, j):
14 root_i = find(i)
15 root_j = find(j)
16 if root_i != root_j:
17 parent[root_i] = root_j
18 return True
19 return False
20
21 total_cost = 0
22 edges_count = 0
23
24 for u, v, cost in connections:
25 if union(u, v):
26 total_cost += cost
27 edges_count += 1
28 if edges_count == N - 1:
29 return total_cost
30
31 return -1