How hard is LeetCode 1135. Connecting Cities With Minimum Cost?

LeetCode 1135. Connecting Cities With Minimum Cost is rated Medium on LeetCode.

What is the time complexity of LeetCode 1135. Connecting Cities With Minimum Cost?

The Python solution on this page runs in O(m \times \log m).

What is the space complexity of LeetCode 1135. Connecting Cities With Minimum Cost?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1135. Connecting Cities With Minimum Cost cover?

LeetCode 1135. Connecting Cities With Minimum Cost is tagged Union Find, Graph, Minimum Spanning Tree and Heap (Priority Queue) on LeetCode.

Is LeetCode 1135. Connecting Cities With Minimum Cost a premium problem?

Yes. LeetCode 1135. Connecting Cities With Minimum Cost is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Connecting Cities With Minimum Cost — LeetCode 1135 Python Solution

MediumLeetCode PremiumUnion FindGraphMinimum Spanning TreeHeap (Priority Queue)

Problem: #1135
Pattern: Union-Find
Reading time: 4 min
Source: leetcode.com

The 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.

Example

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.

Python solution

Python

class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        connections.sort(key=lambda x: x[2])
        p = list(range(n))
        ans = 0
        for x, y, cost in connections:
            x, y = x - 1, y - 1
            if find(x) == find(y):
                continue
            p[find(x)] = find(y)
            ans += cost
            n -= 1
            if n == 1:
                return ans
        return -1

Complexity

Measure	Complexity
Time	O(m \times \log m)
Space	O(n) auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1135. Connecting Cities With Minimum Cost is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1135. Connecting Cities With Minimum Cost?: LeetCode 1135. Connecting Cities With Minimum Cost is rated Medium on LeetCode.
What is the time complexity of LeetCode 1135. Connecting Cities With Minimum Cost?: The Python solution on this page runs in O(m \times \log m).
What is the space complexity of LeetCode 1135. Connecting Cities With Minimum Cost?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1135. Connecting Cities With Minimum Cost cover?: LeetCode 1135. Connecting Cities With Minimum Cost is tagged Union Find, Graph, Minimum Spanning Tree and Heap (Priority Queue) on LeetCode.
Is LeetCode 1135. Connecting Cities With Minimum Cost a premium problem?: Yes. LeetCode 1135. Connecting Cities With Minimum Cost is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.