Problem Description

You have n cities numbered from 1 to n. You're given an array connections where each element connections[i] = [xi, yi, costi] represents a bidirectional connection between city xi and city yi with a cost of costi.

Your task is to find the minimum total cost to connect all n cities such that every city can reach every other city through some path of connections. If it's impossible to connect all cities, return -1.

The total cost is calculated as the sum of all the connection costs you choose to use.

For example, if you have 3 cities and connections [[1,2,5], [1,3,6], [2,3,1]], you could connect all cities by using the connections between cities 1-2 (cost 5) and cities 2-3 (cost 1), giving a total minimum cost of 6. The connection between cities 1-3 is not needed since city 1 can already reach city 3 through city 2.

The problem essentially asks you to build a network that connects all cities using the least expensive set of connections, which is a classic minimum spanning tree problem where you need to find the subset of edges that connects all vertices with the minimum total weight.

Intuition

When we need to connect all cities with minimum cost, we're essentially building a network where every city can reach every other city. This is exactly what a spanning tree does - it connects all nodes in a graph with the minimum number of edges (exactly n-1 edges for n nodes).

Since we want to minimize the total cost, we need a minimum spanning tree. The key insight is that we should greedily pick the cheapest connections available, but we need to be smart about it - we shouldn't create cycles (redundant connections) because they add cost without providing any additional connectivity.

Think of it like building a road network between cities. If cities A and B are already connected (either directly or through other cities), adding another road between them would be wasteful. We only want to add a new road if it connects previously unconnected regions.

This leads us to Kruskal's algorithm:

1. Sort all connections by cost (cheapest first)
2. Go through connections one by one
3. For each connection, check if it connects two different groups of cities
4. If yes, use this connection and merge the groups
5. If no, skip it (it would create a cycle)

To efficiently track which cities are already connected, we use a Union-Find (Disjoint Set Union) data structure. Each city initially forms its own group. When we add a connection, we merge the groups of the two cities. The find operation tells us which group a city belongs to, and if two cities have the same group leader, they're already connected.

We keep track of how many separate groups we have (initially n groups). Each successful connection reduces this by 1. When we have exactly 1 group left, all cities are connected and we return the total cost. If we process all connections and still have multiple groups, it means some cities can't be connected, so we return -1.

Learn more about Union Find, Graph, Minimum Spanning Tree and Heap (Priority Queue) patterns.

Solution Approach

The solution implements Kruskal's algorithm with Union-Find to find the minimum spanning tree:

Step 1: Sort Connections by Cost

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

We sort all connections in ascending order by their cost (index 2). This ensures we always consider the cheapest available connections first.

Step 2: Initialize Union-Find Structure

p = list(range(n))

Create a parent array p where p[i] = i initially. Each city is its own parent, representing n separate components.

Step 3: Find Operation with Path Compression

def find(x):
    if p[x] != x:
        p[x] = find(p[x])  # Path compression
    return p[x]

The find function returns the root parent of a city. Path compression optimization makes future lookups faster by directly connecting nodes to their root.

Step 4: Process Each Connection

for x, y, cost in connections:
    x, y = x - 1, y - 1  # Convert to 0-indexed
    if find(x) == find(y):
        continue  # Skip if already connected

For each connection, convert cities from 1-indexed to 0-indexed. Check if the two cities are already in the same component using find. If they share the same root, adding this edge would create a cycle, so skip it.

Step 5: Union Operation and Cost Accumulation

p[find(x)] = find(y)  # Union the components
ans += cost           # Add cost to total
n -= 1               # Reduce component count

If the cities are in different components:

• Union them by making one root the parent of the other
• Add the connection cost to our running total
• Decrease the component count by 1

Step 6: Check for Complete Connection

if n == 1:
    return ans
return -1

If we reach exactly 1 component (all cities connected), return the total cost. If we process all connections and still have multiple components, some cities remain disconnected, so return -1.

The algorithm has time complexity O(E log E) for sorting edges, where E is the number of connections, and nearly O(E) for the union-find operations with path compression.

Example Walkthrough

Let's walk through a concrete example with 4 cities and the following connections:

• n = 4
• connections = [[1,2,3], [3,4,4], [1,4,7], [2,3,5]]

Initial Setup:

• Sort connections by cost: [[1,2,3], [3,4,4], [2,3,5], [1,4,7]]
• Parent array p = [0, 1, 2, 3] (0-indexed, each city is its own parent)
• Component count = 4, Total cost = 0

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

• Convert to 0-indexed: cities 0 and 1
• find(0) = 0, find(1) = 1 (different components)
• Union: Set p[0] = 1 (connect component 0 to component 1)
• Add cost: Total cost = 3
• Component count = 3
• Current forest: {0,1}, {2}, {3}

Step 2: Process connection [3,4,4]

• Convert to 0-indexed: cities 2 and 3
• find(2) = 2, find(3) = 3 (different components)
• Union: Set p[2] = 3 (connect component 2 to component 3)
• Add cost: Total cost = 3 + 4 = 7
• Component count = 2
• Current forest: {0,1}, {2,3}

Step 3: Process connection [2,3,5]

• Convert to 0-indexed: cities 1 and 2
• find(1) = 1, find(2) = 3 (through path compression: 2→3)
• Different components, so connect them
• Union: Set p[1] = 3 (connect component {0,1} to component {2,3})
• Add cost: Total cost = 7 + 5 = 12
• Component count = 1
• All cities now connected: {0,1,2,3}

Result: Since component count = 1, all cities are connected. Return total cost = 12.

Note that the connection [1,4,7] is never used because by the time we would consider it, cities 1 and 4 (0 and 3 in 0-indexed) are already connected through the path 0→1→3, making this edge redundant.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × log m + m × α(n)) which simplifies to O(m × log m)

The time complexity is dominated by:

1. Sorting the connections array: O(m × log m) where m is the number of edges (connections)
2. The for loop iterates through all m connections: O(m)
3. Each iteration performs find() operations which take O(α(n)) amortized time with path compression, where α is the inverse Ackermann function (effectively constant for practical purposes)
4. Overall: O(m × log m + m × α(n)) ≈ O(m × log m) since the sorting term dominates

Space Complexity: O(n)

The space complexity comes from:

1. The parent array p which stores n elements: O(n)
2. The sorting operation uses O(log m) space for the recursive call stack in Python's Timsort
3. The recursion depth of find() can be at most O(n) in the worst case before path compression, but with path compression it becomes much smaller
4. Overall: O(n) as the parent array dominates the space usage

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Convert Between 1-indexed and 0-indexed

One of the most common mistakes is forgetting that cities are numbered from 1 to n, while array indices typically start from 0.

Incorrect Implementation:

def minimumCost(self, n: int, connections: List[List[int]]) -> int:
    parent = list(range(n))
  
    for city1, city2, cost in connections:
        # WRONG: Using 1-indexed cities directly as array indices
        root1 = find(city1)  # This will cause IndexError when city1 = n
        root2 = find(city2)

Why it fails: When accessing parent[n] with a parent array of size n (indices 0 to n-1), you'll get an IndexError.

Correct Implementation:

for city1, city2, cost in connections:
    # Convert to 0-indexed before using as array indices
    city1_idx = city1 - 1
    city2_idx = city2 - 1
  
    root1 = find(city1_idx)
    root2 = find(city2_idx)

2. Incorrect Union Operation Without Finding Roots

Another frequent error is directly unioning the nodes instead of their roots, which doesn't properly merge the components.

Incorrect Implementation:

if find(city1_idx) != find(city2_idx):
    # WRONG: Connecting nodes directly instead of their roots
    parent[city1_idx] = city2_idx
    total_cost += cost
    num_components -= 1

Why it fails: This creates inconsistent parent relationships. Nodes in the same tree might not recognize they're connected because their roots weren't properly unified.

Correct Implementation:

root1 = find(city1_idx)
root2 = find(city2_idx)

if root1 != root2:
    # Connect the roots of the two components
    parent[root1] = root2
    total_cost += cost
    num_components -= 1

3. Not Tracking Component Count Correctly

Some implementations try to count components at the end instead of tracking them during the process.

Incorrect Implementation:

def minimumCost(self, n: int, connections: List[List[int]]) -> int:
    # ... union-find operations ...
  
    # WRONG: Trying to count components at the end
    components = len(set(find(i) for i in range(n)))
    return total_cost if components == 1 else -1

Why it fails: This approach works but is inefficient and can be error-prone if the find function isn't implemented correctly or if path compression isn't applied consistently.

Correct Implementation:

num_components = n  # Start with n separate components

for city1, city2, cost in connections:
    # ... find roots ...
  
    if root1 != root2:
        parent[root1] = root2
        total_cost += cost
        num_components -= 1  # Track as we merge
      
        if num_components == 1:  # Early termination
            return total_cost

return -1  # Not all cities connected

The early termination optimization also improves efficiency by avoiding processing unnecessary edges once all cities are connected.