Efficient Cost: Minimize Total Cost to Connect All Nodes in a Network

Question

## Problem

You are given `n` nodes and a list of potential edges, each with a cost. Find the minimum total cost to connect all nodes (i.e., build a minimum spanning tree). If it is impossible to connect all nodes, return -1.

```python
from typing import List

def min_connection_cost(n: int, edges: List[List[int]]) -> int:
    # n: number of nodes (1-indexed)
    # edges: [[node_a, node_b, cost], ...]
    # return: minimum total cost, or -1 if not fully connectable
    pass
```

**Example:**
```
n = 4
edges = [[1,2,3],[1,3,1],[2,3,2],[2,4,4],[3,4,1]]

MST edges: (1,3,1), (3,4,1), (1,2,3) or (2,3,2)
Minimum cost = 1+1+2 = 4
Output: 4
```

## Approach

Kruskal's with Union-Find: sort edges by cost, greedily add edges that don't form a cycle. Time: O(E log E).

## Follow-ups

1. When would you prefer Prim's algorithm over Kruskal's?
2. What if some nodes already have a free connection (cost = 0) — does the algorithm change?
3. How would you find the second-minimum spanning tree?
4. In a distributed setting with millions of edges, how would you compute MST across partitioned data?

Efficient Cost: Minimize Total Cost to Connect All Nodes in a Network

Question Details

Full Details

Topics

More from Snowflake