LeetCode 1135 - Connecting Cities With Minimum Cost

This problem asks us to connect n cities together using a set of possible bidirectional connections. Each connection has a cost, and our goal is to connect every city while minimizing the total cost.

leetcodemediumunion-findgraph-theoryheap-(priority-queue)minimum-spanning-tree

LeetCode Problem 1135

Difficulty: 🟡 Medium
Topics: Union-Find, Graph Theory, Heap (Priority Queue), Minimum Spanning Tree

Solution

Problem Understanding

This problem asks us to connect n cities together using a set of possible bidirectional connections. Each connection has a cost, and our goal is to connect every city while minimizing the total cost.

More formally, we are given:

  • An integer n, representing cities labeled from 1 to n

  • A list connections, where each element is [x, y, cost]

  • x and y are two cities

  • cost is the price required to build a road between them

We must choose some subset of these connections such that:

  1. Every city becomes reachable from every other city
  2. The total cost is as small as possible

If it is impossible to connect all cities, we return -1.

This is a classic graph problem. We can think of:

  • Cities as graph nodes
  • Connections as weighted edges

The task becomes finding a Minimum Spanning Tree, commonly abbreviated as MST.

A spanning tree is a subset of edges that:

  • Connects all vertices
  • Contains no cycles
  • Uses exactly n - 1 edges

A minimum spanning tree is the spanning tree with the smallest possible total edge weight.

The constraints are important:

  • n <= 10^4
  • connections.length <= 10^4

These limits are too large for exponential or brute-force subset generation approaches. We need a near-linear or O(E log E) solution, where E is the number of edges.

Some important edge cases include:

  • The graph is disconnected, meaning some cities can never be reached
  • Multiple edges exist between the same pair of cities
  • Costs can be zero
  • There may already be exactly n - 1 edges
  • There may be many redundant edges that create cycles

A correct solution must efficiently determine both:

  1. Whether all cities can be connected
  2. What the minimum total connection cost is

Approaches

Brute Force Approach

A brute-force solution would try every possible subset of edges and determine whether that subset connects all cities.

For each subset, we would:

  1. Build the graph using only those edges
  2. Check whether all cities are connected
  3. Compute the total cost
  4. Track the minimum valid cost

This approach is correct because it examines every possible combination of edges, guaranteeing that the minimum valid solution will eventually be found.

However, this is computationally infeasible.

If there are E edges, then there are 2^E possible subsets. With up to 10^4 edges, the number of subsets becomes astronomically large.

Even checking connectivity for each subset would add additional cost, making this approach completely impractical.

Optimal Approach, Kruskal's Algorithm with Union-Find

The key insight is that we do not need to test every subset.

This problem is exactly the Minimum Spanning Tree problem, and Kruskal's Algorithm solves it efficiently.

Kruskal's Algorithm works by:

  1. Sorting all edges by cost
  2. Repeatedly taking the cheapest edge that does not form a cycle

To efficiently determine whether adding an edge creates a cycle, we use the Union-Find data structure, also called Disjoint Set Union, abbreviated DSU.

Union-Find supports two efficient operations:

  • find(x) determines which connected component a node belongs to
  • union(x, y) merges two components if they are different

If two cities are already in the same component, adding another edge between them would create a cycle, so we skip it.

This greedy strategy works because the minimum spanning tree property guarantees that choosing the cheapest safe edge at every step produces the optimal result.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^E * (V + E)) O(V + E) Tries every subset of edges
Optimal, Kruskal + Union-Find O(E log E) O(V) Efficient MST construction

Algorithm Walkthrough

Step 1: Sort all connections by cost

We first sort the edges in ascending order of their connection cost.

This ensures that we always consider the cheapest available edge first. Since we want the minimum total cost, choosing cheaper edges early is essential.

Step 2: Initialize the Union-Find structure

We create a Union-Find data structure where initially every city belongs to its own component.

At this stage:

  • Each city is disconnected
  • The parent of each city is itself

We also initialize:

  • total_cost = 0
  • edges_used = 0

Step 3: Process edges in sorted order

We iterate through each edge [city1, city2, cost].

For each edge:

  1. Find the root parent of city1
  2. Find the root parent of city2
  3. If the roots are different:
  • The edge connects two separate components
  • Add the edge to the MST
  • Union the two components
  • Add the cost to total_cost
  • Increment edges_used

If the roots are the same:

  • The cities are already connected
  • Adding this edge would create a cycle
  • We skip it

Step 4: Stop once we have n - 1 edges

A spanning tree for n nodes always contains exactly n - 1 edges.

Once we reach this count, all cities are connected, and we can stop processing further edges.

Step 5: Verify connectivity

After processing all edges:

  • If edges_used == n - 1, we successfully connected all cities
  • Otherwise, the graph was disconnected, so we return -1

Why it works

Kruskal's Algorithm relies on the cut property of minimum spanning trees.

At every step, the algorithm selects the cheapest edge that connects two previously disconnected components. This guarantees that we never miss a cheaper valid solution.

Union-Find ensures that cycles are avoided efficiently, so the resulting structure remains a tree.

Because we always choose the minimum safe edge, the final spanning tree has the minimum possible total cost.

Python Solution

from typing import List

class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:
        parent = list(range(n + 1))
        rank = [0] * (n + 1)

        def find(city: int) -> int:
            if parent[city] != city:
                parent[city] = find(parent[city])
            return parent[city]

        def union(city1: int, city2: int) -> bool:
            root1 = find(city1)
            root2 = find(city2)

            if root1 == root2:
                return False

            if rank[root1] < rank[root2]:
                parent[root1] = root2
            elif rank[root1] > rank[root2]:
                parent[root2] = root1
            else:
                parent[root2] = root1
                rank[root1] += 1

            return True

        connections.sort(key=lambda edge: edge[2])

        total_cost = 0
        edges_used = 0

        for city1, city2, cost in connections:
            if union(city1, city2):
                total_cost += cost
                edges_used += 1

                if edges_used == n - 1:
                    return total_cost

        return -1

The implementation begins by creating the Union-Find structure.

The parent array tracks the representative parent for each city. Initially, every city is its own parent because no cities are connected.

The rank array helps keep the Union-Find tree balanced. This improves performance by preventing excessively deep trees.

The find function uses path compression. Whenever we search for the root of a city, we update intermediate nodes to point directly to the root. This significantly speeds up future operations.

The union function merges two components if they are different. If the cities already share the same root, the function returns False, indicating that adding the edge would create a cycle.

Next, the connections are sorted by edge cost. This is the core requirement of Kruskal's Algorithm.

We then iterate through the sorted edges. Whenever an edge successfully connects two previously disconnected components, we:

  • Add its cost to the answer
  • Increment the number of used edges

As soon as we use n - 1 edges, we know we have formed a spanning tree, so we return the result immediately.

If the loop finishes before enough edges are added, the graph is disconnected, and we return -1.

Go Solution

package main

import "sort"

func minimumCost(n int, connections [][]int) int {
	parent := make([]int, n+1)
	rank := make([]int, n+1)

	for i := 1; i <= n; i++ {
		parent[i] = i
	}

	var find func(int) int

	find = func(city int) int {
		if parent[city] != city {
			parent[city] = find(parent[city])
		}
		return parent[city]
	}

	union := func(city1, city2 int) bool {
		root1 := find(city1)
		root2 := find(city2)

		if root1 == root2 {
			return false
		}

		if rank[root1] < rank[root2] {
			parent[root1] = root2
		} else if rank[root1] > rank[root2] {
			parent[root2] = root1
		} else {
			parent[root2] = root1
			rank[root1]++
		}

		return true
	}

	sort.Slice(connections, func(i, j int) bool {
		return connections[i][2] < connections[j][2]
	})

	totalCost := 0
	edgesUsed := 0

	for _, edge := range connections {
		city1 := edge[0]
		city2 := edge[1]
		cost := edge[2]

		if union(city1, city2) {
			totalCost += cost
			edgesUsed++

			if edgesUsed == n-1 {
				return totalCost
			}
		}
	}

	return -1
}

The Go implementation closely mirrors the Python version.

Go does not support nested named functions in the same way as Python, so find is declared as a function variable before assignment.

Slices are used for both parent and rank. Since city labels begin at 1, the arrays are allocated with size n + 1.

The sorting step uses sort.Slice, which allows custom comparison logic.

Integer overflow is not a concern here because the maximum possible cost remains safely within Go's int range under the given constraints.

Worked Examples

Example 1

Input:

n = 3
connections = [[1,2,5],[1,3,6],[2,3,1]]

Step 1: Sort edges by cost

Edge Cost
[2,3] 1
[1,2] 5
[1,3] 6

Step 2: Initial state

City Parent
1 1
2 2
3 3 
total_cost = 0
edges_used = 0

Step 3: Process edge [2,3,1]

  • City 2 root = 2
  • City 3 root = 3
  • Different components, union them

Updated state:

City Parent
1 1
2 2
3 2 
total_cost = 1
edges_used = 1

Step 4: Process edge [1,2,5]

  • City 1 root = 1
  • City 2 root = 2
  • Different components, union them

Updated state:

City Parent
1 1
2 1
3 2 
total_cost = 6
edges_used = 2

Now edges_used == n - 1, so we stop.

Final answer:

6

Example 2

Input:

n = 4
connections = [[1,2,3],[3,4,4]]

Step 1: Sort edges

Edge Cost
[1,2] 3
[3,4] 4

Step 2: Initial state

City Parent
1 1
2 2
3 3
4 4

Step 3: Process edge [1,2,3]

Union successful.

total_cost = 3
edges_used = 1

Step 4: Process edge [3,4,4]

Union successful.

total_cost = 7
edges_used = 2

The loop ends.

We need n - 1 = 3 edges, but only used 2.

This means the graph is disconnected.

Final answer:

-1

Complexity Analysis

Measure Complexity Explanation
Time O(E log E) Sorting edges dominates the runtime
Space O(V) Union-Find arrays store parent and rank

The most expensive operation is sorting the connections array, which takes O(E log E) time.

Union-Find operations are extremely efficient due to path compression and union by rank. Their amortized complexity is nearly constant, technically O(alpha(V)), where alpha is the inverse Ackermann function.

Since alpha(V) grows extremely slowly, it is treated as constant in practice.

The space usage comes primarily from the parent and rank arrays, each of size n + 1.

Test Cases

from typing import List

class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:
        parent = list(range(n + 1))
        rank = [0] * (n + 1)

        def find(city: int) -> int:
            if parent[city] != city:
                parent[city] = find(parent[city])
            return parent[city]

        def union(city1: int, city2: int) -> bool:
            root1 = find(city1)
            root2 = find(city2)

            if root1 == root2:
                return False

            if rank[root1] < rank[root2]:
                parent[root1] = root2
            elif rank[root1] > rank[root2]:
                parent[root2] = root1
            else:
                parent[root2] = root1
                rank[root1] += 1

            return True

        connections.sort(key=lambda edge: edge[2])

        total_cost = 0
        edges_used = 0

        for city1, city2, cost in connections:
            if union(city1, city2):
                total_cost += cost
                edges_used += 1

                if edges_used == n - 1:
                    return total_cost

        return -1

solution = Solution()

assert solution.minimumCost(
    3,
    [[1, 2, 5], [1, 3, 6], [2, 3, 1]]
) == 6  # Basic MST example

assert solution.minimumCost(
    4,
    [[1, 2, 3], [3, 4, 4]]
) == -1  # Disconnected graph

assert solution.minimumCost(
    1,
    []
) == 0  # Single city requires no edges

assert solution.minimumCost(
    2,
    [[1, 2, 0]]
) == 0  # Zero-cost edge

assert solution.minimumCost(
    4,
    [[1, 2, 1], [2, 3, 2], [3, 4, 3]]
) == 6  # Already a tree

assert solution.minimumCost(
    4,
    [[1, 2, 1], [2, 3, 2], [3, 4, 3], [1, 4, 100]]
) == 6  # Expensive redundant edge skipped

assert solution.minimumCost(
    3,
    [[1, 2, 1], [2, 3, 2], [1, 3, 10]]
) == 3  # Cycle edge skipped

assert solution.minimumCost(
    5,
    [[1, 2, 1], [2, 3, 1], [3, 4, 1], [4, 5, 1], [1, 5, 50]]
) == 4  # Long chain preferred over expensive shortcut
Test Why
Example 1 Validates standard MST construction
Example 2 Validates disconnected graph handling
Single city Ensures trivial graph works correctly
Zero-cost edge Confirms zero weights are handled
Already a tree Verifies no unnecessary edges added
Expensive redundant edge Ensures cycles are skipped
Triangle graph Confirms cheapest cycle-breaking behavior
Long chain vs shortcut Verifies greedy edge selection

Edge Cases

Disconnected Graph

One major edge case occurs when the graph cannot fully connect all cities.

For example:

n = 4
connections = [[1,2,1],[3,4,1]]

There are two separate components with no bridge between them.

A buggy implementation might incorrectly return the sum of all edges. However, a valid spanning tree must contain exactly n - 1 edges.

Our implementation tracks edges_used, and only returns the total cost if exactly n - 1 edges were successfully added.

Otherwise, it returns -1.

Graph with Cycles

Another important case occurs when multiple edges create cycles.

Example:

[[1,2,1],[2,3,2],[1,3,3]]

A naive implementation might include all three edges, creating a cycle and increasing the total cost unnecessarily.

Union-Find prevents this issue by checking whether two cities already belong to the same connected component before adding an edge.

If they are already connected, the edge is skipped.

Single City

When n = 1, no edges are required because the single city is already connected to itself.

This case can easily cause off-by-one errors.

Our implementation handles it naturally:

  • n - 1 = 0
  • No edges are processed
  • The minimum cost is correctly 0

Multiple Equal-Cost Edges

Sometimes several edges have the same weight.

Example:

[[1,2,1],[2,3,1],[1,3,1]]

The MST is not unique in this scenario.

Kruskal's Algorithm still works correctly because any minimum-cost valid spanning tree is acceptable. The sorting order among equal-cost edges does not affect correctness.