> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Connecting Cities With Minimum Cost

> Tested Python solution for LeetCode 1135 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 1135, [Medium](/catalog/medium). Topics: [Union Find](/catalog/topics/union-find), [Graph](/catalog/topics/graph), Minimum Spanning Tree, [Heap (Priority Queue)](/catalog/topics/heap-priority-queue). [View on LeetCode](https://leetcode.com/problems/connecting-cities-with-minimum-cost/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1135   # by problem number
lcpy gen -s connecting_cities_with_minimum_cost   # by problem name
```

## Problem

There are `n` cities labeled from `1` to `n`. You are given the integer `n` and an array `connections` where `connections[i] = [xi, yi, costi]` indicates that the cost of connecting city `xi` and city `yi` (bidirectional connection) is `costi`.

Return *the minimum **cost** to connect all the* `n` *cities such that there is at least one path between each pair of cities*. If it is impossible to connect all the `n` cities, return `-1`.

The **cost** is the sum of the connections' costs used.

### Examples

![Example 1](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1100-1199/1135.Connecting%20Cities%20With%20Minimum%20Cost/images/1314_ex2.png)

```
Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.
```

![Example 2](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1100-1199/1135.Connecting%20Cities%20With%20Minimum%20Cost/images/1314_ex1.png)

```
Input: n = 4, connections = [[1,2,3],[3,4,4]]
Output: -1
Explanation: There is no way to connect all cities even if all edges are used.
```

### Constraints

* 1 \<= n \<= 10^4
* 1 \<= connections.length \<= 10^4
* connections\[i].length == 3
* 1 \<= xi, yi \<= n
* xi != yi
* 0 \<= costi \<= 10^5

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/connecting_cities_with_minimum_cost/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/connecting_cities_with_minimum_cost/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(m log m) where m = len(connections)
    # Space: O(n)
    def minimum_cost(self, n: int, connections: list[list[int]]) -> int:
        parent = list(range(n + 1))
        rank = [0] * (n + 1)

        def find(node: int) -> int:
            root = node
            while parent[root] != root:
                root = parent[root]
            while parent[node] != root:
                parent[node], node = root, parent[node]
            return root

        total = 0
        edges_used = 0
        for x, y, cost in sorted(connections, key=lambda edge: edge[2]):
            rx, ry = find(x), find(y)
            if rx == ry:
                continue
            if rank[rx] < rank[ry]:
                rx, ry = ry, rx
            parent[ry] = rx
            if rank[rx] == rank[ry]:
                rank[rx] += 1
            total += cost
            edges_used += 1
            if edges_used == n - 1:
                return total
        return total if edges_used == n - 1 else -1
```

## Complexity

| Time | Space |
| - | - |
| O(m log m) where m = len(connections) | O(n) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.